本站使用了 Pjax 等基于 JavaScript 的开发技术,但您的浏览器已禁用 JavaScript,请开启 JavaScript 以保证网站正常显示!

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

目前,我采用的是迪杰斯特拉算法计算所有点的最短路径(感觉弗洛伊德算法会更好些?)。迪杰斯特拉算法算的是单源(V_begin)到所有点的最短距离,也就是说需要遍历一次所有的点。

遍历V_begin

for (int V_begin = 0; V_begin < G->m_CrossRoad_v.size(); V_begin++) {
}
下面是迪杰斯特拉算法的流程

1. 声明dist数组

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

2. 初始化顶点集

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 ;}
        }
    }
}
———— 本文结束 感谢阅读 ————

推广

 继续浏览关于 Traffic-Network-Model 的文章

 本文最后更新于:2019/03/21 15:38:04,可能因经年累月而与现状有所差异

 引用转载请注明:指尖魔法屋 > 学习笔记 > 毕业设计番外篇(一)之车辆路径的计算