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

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

        }

    }

}