毕业设计番外篇(一)之车辆路径的计算

for (int V_begin = 0; V_begin < G->m_CrossRoad_v.size(); V_begin++) {
}

vector<double> Determined_dist(G->m_CrossRoad_v.size(), 0.0);

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 ;}
        }
    }
}