选择最佳线路（二）

如何要改进？

在上文中，讨论了最佳线路计算的数据结构的算法。但在交通线路的描述中，对网站线路孤立的起点，为了防止计算中无效循环，人为增加了下一结点为-1的虚拟点。但增加结点ID为-1的点，与现实不符。本文试图取消ID为-1的结点，并对算法进行修改。

修改后的深圳地铁的描述为

string[] nsStr =["1:1","0:1>2:1>6:1>16:1","1:4>3:6>7:3>15:1","2:1>4:2>9:3>15:1","3:2>15:1>10:3","6:4","1:6>5:3>7:5>11:1","8:1>2:1>9:1","7:1>9:1>12:1","7:1>8:1>10:1>3:1","4:1>9:1","6:1>12:1","8:1>11:1>13:1>14:1","12:1","12:1","2:1>3:1>4:1>20:1>21:1","1:1>18:1","18:1","16:1>17:1>19:1>20:1","18:1>20:1","18:1>19:1>15:1","15:1"];for(int i=0;i<nsStr.Length;i++){
       ns =newNodeStation(i, nsStr[i]);
       lns.Add(ns);}

算法修改为

publicboolFindNodeWay(List<NodeStation> lns,List<NodeWay> listWay,int start,int end){bool b =false, first, arrive =false;string s0, s1, s2;string[] sa, sb;int dist0 =0, d1, nextStation;NodeStation ns;NodeWay nw, nw0;if(listWay.Count ==0){
         ns = lns[start];
         sa = ns.Child.Split(">");for(int i =0; i < sa.Length; i++){
             sb = sa[i].Split(":");if(sb.Length >1){
                 nw =newNodeWay();
                 nw.Next =int.Parse(sb[0]);
                 nw.WayStr =$">{start}>{nw.Next}>";
                 nw.Distance =int.Parse(sb[1]);
                 listWay.Add(nw);}}}for(int i =0; i < listWay.Count; i++){              
         nw = listWay[i];
         s0 = nw.WayStr;
         dist0 = nw.Distance;
         first =true;if(!nw.Arrive){
             ns = lns[nw.Next];
             sa = ns.Child.Split(">");for(int j =0; j < sa.Length; j++){
                 sb = sa[j].Split(":");if(sb.Length >1){
                     nextStation =int.Parse(sb[0]);
                     d1 =int.Parse(sb[1]);
                     s1 =$">{nextStation}>";
                     s2 =$"{nextStation}>";if(!nw.WayStr.Contains(s1)){
                         arrive = nextStation ==end ?true:false;if(first){
                             first =false;
                             nw.Arrive = arrive;
                             nw.Next = nextStation;
                             nw.Distance = dist0 + d1;;
                             nw.WayStr = s0 + s2;}else{
                             nw0 =newNodeWay();
                             nw0.WayStr = s0 + s2;
                             nw0.Next = nextStation;
                             nw0.Arrive = arrive;
                             nw0.Distance = dist0 + d1;
                             listWay.Add(nw0);}}}}if(first){
                 listWay.RemoveAt(i);}
             i =-1;}}return b;}

改进后的作用

 按上述改进后，有两方面的提升

1.线路描述更加直观,简洁。

2.线路计算由于不再进行-1结点判断，效率提升。只要线路无新增结点，立即删除，减少剩余计算量。