毕业设计番外篇(一)之车辆路径的计算
最短路径这种活，适合关在小黑屋里算完再喂给主程序。
这篇是番外，不参与每次仿真的主循环。 思路篇(一) 建好 Graph 之后，需要一批「从某路口到其它路口的最短路径」，供整理成 route.txt，再由 思路篇(三) 的 loadRoute 读入。我采用的是 Dijkstra：单源到所有点的最短路，外层再对每个路口作为源点跑一遍。当时也琢磨过 Floyd 一次出全源，但路口规模不大，多次 Dijkstra 写起来更顺手，内存也够用。
目前，我采用的是迪杰斯特拉算法计算所有点的最短路径（感觉弗洛伊德算法会更好些？）。迪杰斯特拉算法算的是单源（V_begin)到所有点的最短距离，也就是说需要遍历一次所有的点。
遍历 V_begin
外层循环把每个路口下标当作源点 V_begin：
for (int V_begin = 0; V_begin < G->m_CrossRoad_v.size(); V_begin++) {
}
对固定源点，内层是标准 Dijkstra：S 标记是否已确定最短路，dist 存当前最佳距离，compare_dist 用来每轮找未确定集合里距离最小的点，path[j] 记录 j 的前驱路口下标，回溯时能还原路径。
下面是迪杰斯特拉算法的流程
1. 声明 dist 数组
文中片段里还有一处 Determined_dist 的声明，和主实现里的 dist 同类，都是按路口数量开向量；真正参与松弛的是下面 calcShortestPath 里的那组。
vector<double> Determined_dist(G->m_CrossRoad_v.size(), 0.0);
2. 初始化顶点集
从源点 V_begin 出发，先把源点放进 S，距离置 0，前驱 -1。再扫描源点 JunctionRoad 里每条出边，用对应 Road 的 m_dLength 松弛直连邻居，写入 dist 和 compare_dist。
主循环跑 size-1 轮：每轮在 compare_dist 里找当前最小且未确定的点 min_element_index，标记进 S，再对它的所有出边尝试松弛——若 dist[next] > dist[current] + 边长，则更新距离并把 path[next] = current。边权来自 G->m_Road_v[crossroad.outRoadID].m_dLength，邻居路口是 m_CrossRoadToSite。
void calcShortestPath(Graph *G) {
int currentPointSite,nextPointSite;
ofstream PointPathFile(DIR_RES"PointPath.txt"),RoadPathFile(DIR_RES"RoadPath.txt");
//对点进行的一级遍历
for (int V_begin = 0; V_begin < G->m_CrossRoad_v.size(); V_begin++) {
// =================== 迪杰斯特拉算法开始 ===============================
vector<bool> S(G->m_CrossRoad_v.size(), false); //判断是否选中
vector<double> dist(G->m_CrossRoad_v.size(), DBL_MAX/2);// dist
vector<double> compare_dist(G->m_CrossRoad_v.size(), DBL_MAX/2);// 辅助dist用来取最短距离点
vector<int> path(G->m_CrossRoad_v.size(),-2); // path
S[V_begin] = true;
path[V_begin] = -1;
for(auto crossroad : G->m_CrossRoad_v[V_begin].JunctionRoad){
nextPointSite = G->m_Road_v[crossroad.outRoadID].m_CrossRoadToSite;
dist[nextPointSite] = G->m_Road_v[crossroad.outRoadID].m_dLength;
compare_dist[nextPointSite] = dist[nextPointSite];
}
auto min = min_element(compare_dist.begin(), compare_dist.end());
int min_element_index = distance(compare_dist.begin(), min);
compare_dist[min_element_index] = DBL_MAX/2;
// 循环size-1次
for(int i = 0; i < G->m_CrossRoad_v.size()-1; i++){
for(auto crossroad : G->m_CrossRoad_v[min_element_index].JunctionRoad){
currentPointSite = min_element_index;
nextPointSite = G->m_Road_v[crossroad.outRoadID].m_CrossRoadToSite;
if(S[nextPointSite]){
continue;
}
if(dist[nextPointSite] > dist[currentPointSite] + G->m_Road_v[crossroad.outRoadID].m_dLength) {
dist[nextPointSite] = dist[currentPointSite] + G->m_Road_v[crossroad.outRoadID].m_dLength;
compare_dist[nextPointSite] = dist[nextPointSite];
path[nextPointSite] = currentPointSite;
}
}
min = min_element(compare_dist.begin(), compare_dist.end());
min_element_index = distance(compare_dist.begin(), min);
S[min_element_index] = true;
compare_dist[min_element_index] = DBL_MAX/2;
}
for(int i = 0;i<path.size();i++){
int j = i;
bool flag = false;
while( path[j] >= 0) {
flag = true;
PointPathFile << path[j] << " ";
for(auto node:G->m_CrossRoad_v[j].JunctionRoad){
if(G->m_Road_v[node.outRoadID].m_CrossRoadToSite == path[j]){
RoadPathFile << node.outRoadID << " ";
}
}
j = path[j];
}
if(flag){RoadPathFile << endl;PointPathFile << endl ;}
}
}
}
每个源点跑完后，对目标点 i 沿 path 回溯：一边写路口序列到 PointPath.txt，一边根据「从 j 哪条出边能到前驱 path[j]」查 outRoadID，把道路 id 写入 RoadPath.txt。一行对应一条「源到某终点」的路径。后续手工或脚本把 RoadPath.txt 里需要的行抽成 思路篇(三) 的 route.txt 格式即可。
实现上的细节：DBL_MAX/2 当无穷大是怕加法溢出；min_element 每轮扫全局是 O(V²)，路口少时无所谓，多了可以换优先队列。还有一回 path 初始全是 -2，只有 >= 0 的前驱才参与回溯，避免把不可达点也输出一行空路径。
算路模块和仿真解耦的好处是：改权重、改图结构，只需重跑 calcShortestPath，不用动 runSimulation。系列导航见 汇总篇。
版权声明: 本文首发于 指尖魔法屋-毕业设计番外篇(一)之车辆路径的计算（https://blog.thinkmoon.cn/post/153-graduation-design-notes-cplusplus/） 转载或引用必须申明原指尖魔法屋来源及源地址！