当前位置：首页 > news >正文

如何选择最佳路线？

news 来源：原创 2024/9/13 10:50:03

交通线路的选择

日常交通线路的选择，并不是按最短路径选择的。还要参考道路的等级，道路是否拥堵，道路通行速度等多种情形。本程序列举出所有能通行的线路，并计算出行驶距离，来供用户选择。当然，也可以加入道路实时通行情况，收费情况，并依据用户的偏好，计算出最佳线路。

线路如何描述？

·交通线路纷繁复杂，是一种无序的网状结构。对于线路的描述，本人认为所有的交通图，都是由点互相连通组成的。每个点，如果相连的点为一个，则增加一个虚拟终点。即一个点最少与另外两个点连通。·

数据结构如下：

  public class NodeStation{public int Id;//nodeIdpublic string Child="";//以 nodeId1:distance1>nodeId2:distance2>nodeId3:distance3.....表示子结点List}

线路的描述如下：

 public class NodeWay{public string WayStr="";//>nodeId1>nodeId2>nodeId3表示线路public int Distance;//表示距离public int Time;//表示所需时间public int Next;//表示下一nodepublic bool Arrive=false;//表示是否到达终点}List<NodeWay> listWay 表示所有找到的线路

算法

`1.找到起点（nodeStation)。
2.以起点为当前结点，将起点的所有子点（nodeStation)为起点.重复第一步。
3.若本结点的子结点为虚拟终点，删除本线路。
4若子结点为终点，本线路结束查找。
4.若不是，要么增加线路，要么在原有的线路上重复下一步。

代码

 public bool FindNodeWay(List<NodeStation> lns,List<NodeWay> listWay,int start,int end)
{bool b=false,first,arrive=false;List<int> starts = new List<int>();List<int> dist=new List<int>();string s0,s1,s2;string[] sa,sb;int dist0 = 0, d1, nextStation;NodeStation ns;NodeWay nw,nw0;if (starts.Count == 0){ns = lns[start];sa = ns.Child.Split(">");for (int i = 0; i < sa.Length; i++){sb = sa[i].Split(":");if (sb[0] != "-1"){nw = new NodeWay();nw.Next = int.Parse(sb[0]);nw.WayStr = $">{start}>{nw.Next}>";nw.Distance = int.Parse(sb[1]);listWay.Add(nw);}}}int n = 0;for (int i=0;i<listWay.Count;i++){n++;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(":");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;if (nextStation != -1){nw.Arrive = arrive;nw.Next = nextStation;nw.Distance = dist0 + d1; ;nw.WayStr = s0 + s2;}else{listWay.RemoveAt(i);}}else{if (nextStation != -1){nw0 = new NodeWay();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;
}

在这里插入图片描述

这是深圳地铁图的描述数据

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