Dijkstra算法的c++实现

Dijkstra算法的c++实现

Dijkstra算法：
1 Dijkstra算法解决带权图的单源最短路径问题，权值要不小于0。
2 顶点集合S，保存已经找到的从源点s找到的顶点。
3 顶点集合V，保存剩下的节点，最小优先队列Q，存储V中节点。
4 使用最小优先队列，寻找下一个顶点距离最近的节点u,然后使用w(s,u)来松弛u的邻接点v。
===================================================================

View Code 1 //prev[],dist[],distance[][] 2 #include<iostream> 3 #include<stdio.h> 4 #include<limits.h> 5 using namespace std; 6 const int MAX = 100; 7 int c[MAX][MAX]; 8 int dist[MAX]; 9 int prev[MAX]; 10 int S[MAX]; 11 void dijkstra(int s,int n,int dist[],int prev[],int c[][MAX]) 12 { 13 for(int i = 1; i <= n; i++)//数组下标都从1开始 14 { 15 dist[i] = c[s][i]; 16 S[i] = 0;//0代表，i不再S集合中 17 if(i != s && dist[i] < INT_MAX) 18 prev[i] = s;//i的前一个节点 19 else 20 prev[i] = -1;//prev数组初始化 21 } 22 S[s] = 1;//源点s放在结合S中 23 //选择不在S集合中的具有最短距离的顶点u 24 int u; 25 for(int i = 1; i < n; i++) 26 { 27 int mindis = INT_MAX; 28 for(int j = 1; j <= n; j++) 29 { 30 if(!S[j] && dist[j] < mindis) 31 { 32 u = j; 33 mindis = dist[j]; 34 } 35 } 36 S[u] = 1; 37 for(int k = 1; k <= n; k++) 38 { 39 if(!S[k] && c[u][k] < INT_MAX && dist[u] + c[u][k] < dist[k]) 40 { 41 dist[k] = dist[u] + c[u][k]; 42 prev[k] = u; 43 } 44 } 45 } 46 } 47 int main() 48 { 49 freopen("graph.txt","r",stdin); 50 int line,numberVertex; 51 cin >> numberVertex >> line; 52 //init c[][] 53 for(int i = 1; i <= numberVertex; i++) 54 for(int j = 1; j <= numberVertex; j++) 55 if(i != j) 56 c[i][j] = INT_MAX; 57 //c[][]对角线上为0 58 int p,q,len; 59 for(int i = 1; i <= line; i++) 60 { 61 cin >> p >> q >> len; 62 if(len < c[p][q]) 63 c[p][q] = len; 64 } 65 for(int i =1; i <= numberVertex; i++) 66 { 67 for(int j = 1; j <= numberVertex; j++) 68 cout << c[i][j] << " "; 69 cout << endl; 70 } 71 //init dist[] 72 for(int i = 1; i <= numberVertex; i++) 73 dist[i] = INT_MAX; 74 dijkstra(1,numberVertex,dist,prev,c); 75 cout << dist[numberVertex] << endl; 76 return 0; 77 }

 1 dist[v]保存的是从源点到这个点的最短距离；

 2 prev[v]保存的是从源点到这个点的最短路径中，这个点的前一个节点

 3 c[][]存储的是顶点之间的权值

 

posted on 2013-05-04 16:44 T000ny 阅读(...) 评论(...) 编辑 收藏

转载于:https://www.cnblogs.com/majianbin/archive/2013/05/04/3059630.html

总结

以上是生活随笔为你收集整理的Dijkstra算法的c++实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。