当前位置:   article > 正文

Dijkstra算法(单元点最短路径)

单元点最短路径

Dijkstra算法解决图中某特定点到其他点的最短路径。

迪杰斯塔拉(Dijkstra)算法思想:

按路径长度递增的次序产生最短路径的算法。设集合S存放已经找到最短路径的顶点,V为所有节点的集合,S的初始状态只包含源点V0,对Vi∈V-S。

假设从源点V0到Vi的有向边为最短路径,以后每求得一条最短路V0……Vk,就把Vk加入集合S里,并将路径V0……Vk,Vi与原来的假设比较,取路径较短者为最短路径。

重复上述过程,直到集合V中全部顶点加入集合S里。算法结束。

理解:

①对于集合S和集合V-S,每次迭代都把集合V-S中与源点V0距离最小的点Vk加入集合S

②然后重新计算集合V-S中所有点与V0的最短距离

③如果所有点都已经加入S则结束,否则继续从①开始

  1. /*************************************************************************
  2. > File Name: Dijkstra.cpp
  3. > Author: Shorey
  4. > Mail: shoreybupt@gmail.com
  5. > Created Time: 2015年04月24日 星期五 17时12分25秒
  6. ************************************************************************/
  7. #include<iostream>
  8. #include<stdlib.h>
  9. #include<stdio.h>
  10. #include<stack>
  11. #define M 100
  12. #define N 100
  13. #define INT_MAX 10000
  14. using namespace std;
  15. typedef struct node
  16. {
  17. int matrix[N][M];
  18. int n;
  19. int e;
  20. }MGraph;
  21. void DijkstraPath(MGraph g, int *dist, int *path, int v0)//v0表示源顶点
  22. {
  23. bool *visited = new bool[g.n];
  24. for(int i=0; i<g.n; i++) //初始化工作
  25. {
  26. if(g.matrix[v0][i]>0 && i!=v0)
  27. {
  28. dist[i] = g.matrix[v0][i];
  29. path[i] = v0;
  30. }
  31. else
  32. {
  33. dist[i] = INT_MAX; //若i不与v0直接相邻,则权值为无穷大
  34. path[i] = -1;
  35. }
  36. visited[i] = false;
  37. path[v0] = v0;
  38. dist[v0] = 0;
  39. }
  40. visited[v0] = true; //v0设为已经访问
  41. for(int i=1; i<g.n; i++) //循环n-1次,寻找把剩余结点加入的路径
  42. {
  43. int min = INT_MAX;
  44. int u;
  45. for(int j=0; j<g.n; j++)//寻找未被扩展的权值最小的顶点
  46. {
  47. if(visited[j]==false && dist[j]<min)
  48. {
  49. min = dist[j];
  50. u = j;
  51. }
  52. }
  53. visited[u] = true;//把上步找到的结点加入路径中
  54. for(int k=0; k<g.n; k++)//更新dist数组的值和路径的值
  55. {
  56. if(visited[k]==false && g.matrix[u][k]>0 && min+g.matrix[u][k]<dist[k])
  57. {
  58. dist[k] = min+g.matrix[u][k];
  59. path[k] = u;
  60. }
  61. }
  62. }
  63. }
  64. void showPath(int *path, int v, int v0)
  65. {
  66. stack<int> s;
  67. int u = v;
  68. while(v!=v0)
  69. {
  70. s.push(v);
  71. v = path[v];
  72. }
  73. s.push(v);
  74. while(!s.empty())
  75. {
  76. printf("%d ",s.top());
  77. s.pop();
  78. }
  79. }
  80. int main()
  81. {
  82. int n,e;
  83. while(scanf("%d%d",&n,&e) && e!=0)
  84. {
  85. MGraph g;
  86. int v0;
  87. int *dist = new int[n];
  88. int *path = new int[n];
  89. for(int i=0; i<N; i++)
  90. for(int j=0; j<M; j++)
  91. g.matrix[i][j] = 0;
  92. g.n = n;
  93. g.e = e;
  94. for(int i=0; i<e; i++)
  95. {
  96. int s,t,w;
  97. scanf("%d%d%d",&s,&t,&w);
  98. g.matrix[s][t] = w;
  99. }
  100. scanf("%d",&v0);
  101. DijkstraPath(g, dist, path, v0);
  102. for(int i=0; i<n; i++)
  103. {
  104. if(i!=v0)
  105. {
  106. showPath(path, i, v0);
  107. printf("%d\n",dist[i]);
  108. }
  109. }
  110. }
  111. return 0;
  112. }



声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/在线问答5/article/detail/970019
推荐阅读
相关标签
  

闽ICP备14008679号