加载中......
搜索
注册登录 快速发布
输入验证码，即可复制
微信扫码下载好向圈APP, 登陆后即可进入消息页面查看验证码
只需要3秒时间
使用道具
123480181

2020-11-09 20:12

Djkstra最短路径算法的c++代码实现

Djkstra算法是求解单源（起始点固定）最短路径问题的一种经典方法，它采用了贪心策略（其实我觉得也是动态规划），可以求得图中的一个点到其他所有点的距离，计算复杂度是 O(E|V|)，如果采用最小堆优化可以达到O(ElogV )。算法的整体思想是将顶点分成两类：已经构成最短路的点的集合V1和没有构成最短路的点的集合V2。我们将dist设置为第 i个点到V1的距离，每次将V2中取距离V1集合最短的点P放入V1中，同时因为P被放入了V1，那么其他点到V1的最短路就有可能通过P了，所以我们更新所有集合V2内的点j到V1的距离dist[j] = min( dist[j], dist[i_P] + G[i_P][j] )，其中i_P表示P的下标， G[i_P][j] 表示图中P到j的距离。但是需要注意一点：Djkstra算法不能解决具有负权边的最短路径问题。显然，当具有负权边的时候你无法保证每次放入V1的都是最短路径， 具体可以参考点击打开链接，讲的很清楚。我们以下图为例编写代码，图的左边是最短路的真实结果，右边是图

Djkstra最短路径算法的c++代码实现-1.jpg

#include <iostream>#include<vector>#include<queue>using namespace std; #define MAX_PATH 999999 int shortestId( const vector<int>& dist, const vector<bool>& isShortest ) //寻找当前未放入最短路径集合的所有ID中路径最短的ID号{ int min_dist = MAX_PATH; int min_ID = -1; for(int i = 0; i < dist.size() ; i++) { if(false == isShortest){ if(dist < min_dist){ min_dist = dist; min_ID = i; } } } return min_ID;}vector<int> Djkstra( const vector<vector<int> >& Graph){ int num_vertex = Graph.size(); vector<bool> isShortest( num_vertex, false); //初始化只有第一个顶点（index = 0）被放入最短路的ID集合中 isShortest[0] = true; vector<int> dist(num_vertex, MAX_PATH); //dist表示当前节点 i+1(下标i)到最短路的id集合中所有点的最短距离 dist[0] = 0;  for(int i = 1 ;i < num_vertex; i++) { if(Graph[0] <MAX_PATH) //初始化dist，所有不与1号节点（下标0）相连的设置为正无穷 dist = Graph[0]; } for(int i = 0; i < num_vertex - 1; i++){ int id = shortestId(dist, isShortest); //在所有非最短路的点集合中找到距离最短路集合最近的点，放入最短路集合 isShortest[id] = true; for(int j = 0; j < num_vertex; j++){ //将 id放入最短路集合后，更新所有集合外的元素的距离，他们有可能有通过id的更短路 if( !isShortest[j] ){ dist[j] = min(dist[j], dist[id] + Graph[id][j]); } } } return dist;}void addEdge( const int& startP, const int& endP, const int& weight ,vector<vector<int> >& Graph){ Graph[startP][endP] = weight; //Graph[endP][startP] = weight;} int main(){ vector<vector<int> > Graph(6, vector<int>(6, MAX_PATH) ); addEdge(0,1,10 ,Graph); addEdge(0,5,3 ,Graph); addEdge(1,2,7 ,Graph); addEdge(1,3,5 ,Graph); addEdge(3,0,3,Graph); addEdge(3,2,4,Graph); addEdge(3,4,7,Graph); addEdge(5,1,2,Graph); addEdge(5,3,6,Graph); addEdge(5,4,1,Graph); /* for(int i =0 ; i < Graph.size(); i++) { for(int j = 0; j < Graph.size(); j++) cout << Graph[j] << "\t"; cout <<endl; }*/ vector<int> shortestDist = Djkstra(Graph); for(int i = 0; i <shortestDist.size(); i++) cout <<shortestDist << endl; return 0;}
最后，如果你想学C/C++可以私信小编“01”获取素材资料以及开发工具和听课权限哦！
# 最短路径 # 路径 # 算法 # 代码 # 实现
C语言圈
11161 查看 2 0 反对

说说我的看法高级模式

您需要登录后才可以回帖 登录|立即注册

全部评论
  • rgqnkg116505

    2020-11-10 22:32:46 使用道具

    来自： 中国来自： 中国来自： 中国来自： 中国
    应该用个堆优化下
    回复 0
  • 空城乱人心城dp

    2020-11-11 18:53:52 使用道具

    来自： 北京来自： 北京来自： 北京来自： 北京
    转发了
    回复 0

相关阅读

C语言圈

C语言圈

帖子 27381

 加入 1
百度地图|小黑屋|看往APP（原好向圈） |网站地图
版权所有 © 上海看往信息科技有限公司 | 侵权举报 | 本站法律顾问：上海品道事务所 |违法和不良信息举报电话：17317527721 |举报邮箱：2100458018@qq.com | Wxb | Weifa | 亲爱的市民朋友，上海警方反诈劝阻电话“962110”系专门针对避免您财产被骗受损而设，请您一旦收到来电，立即接听 |封禁账号 | 沪ICP备2022028193号-1