[关闭]
@jtahstu 2017-09-30T10:14:53.000000Z 字数 1077 阅读 1478

单源最短路径算法 - Dijkstra算法

算法


参考《啊哈算法》第六章第二节,PDF在线阅读

介绍

这是一个贪心算法,每次新扩展一个路程最短的点,更新与其相邻的点的路程。

这个算法可以解决单源最短路径问题,这里是从第一个点开始到其他点的最短路径。

不能有负权边,因为扩展到负权边的时候会产生更短的路程,有可能就破坏了已经更新的点路程不会改变的性质。

时间复杂度 O(N^2),使用邻接表表示图,绝大部分情况下能降低时间复杂度,具体看PDF,我也没怎么看懂。

基本思想

每次找到离源点最近的一个顶点,然后以该顶点为中心进行扩展,最终得到源点到其余所有点的最短路径。

代码

  1. /**
  2. * 单源最短路径算法
  3. * Dijkstra算法
  4. * 时间复杂度 O(N^2)
  5. * by jtahstu at 2017-09-18
  6. */
  7. #include <iostream>
  8. #include <climits>
  9. using namespace std;
  10. int main() {
  11. int n, m;
  12. cin >> n >> m;
  13. int e[11][11] = {0}, dis[11] = {0}, book[11] = {0};
  14. for (int i = 1; i <= n; i++)
  15. for (int j = 1; j <= n; j++)
  16. if (i == j)
  17. e[i][j] = 0;
  18. else
  19. e[i][j] = INT_MAX;
  20. int a, b, c;
  21. for (int i = 1; i <= m; i++) {
  22. cin >> a >> b >> c;
  23. e[a][b] = c;
  24. }
  25. for (int i = 1; i <= n; ++i) {
  26. dis[i] = e[1][i];
  27. book[i] = 0;
  28. }
  29. book[1] = 1;
  30. int min, u;
  31. for (int i = 1; i <= n - 1; ++i) { //找出值最小的点去做中转,循环n-1次
  32. min = INT_MAX;
  33. for (int j = 1; j <= n; j++) { //找到离1号顶点最近的顶点,然后该点最短路径值确定
  34. if (book[j] == 0 && min > dis[j]) {
  35. min = dis[j];
  36. u = j;
  37. }
  38. }
  39. book[u] = 1; //标记该点最短路径值已经确定
  40. for (int v = 1; v <= n; v++) {
  41. if (dis[v] > dis[u] + e[u][v] && e[u][v] != INT_MAX) //有出边,且可以通过u点中转一下
  42. dis[v] = dis[u] + e[u][v];
  43. }
  44. }
  45. for (int i = 1; i <= n; i++)
  46. cout << dis[i] << " ";
  47. return 0;
  48. }
  49. /**
  50. 6 8
  51. 1 2 1
  52. 1 3 2
  53. 2 3 3
  54. 2 4 3
  55. 2 5 1
  56. 3 4 5
  57. 4 6 2
  58. 5 6 1
  59. 0 1 2 4 2 3
  60. 6 9
  61. 1 2 1
  62. 1 3 12
  63. 2 3 9
  64. 2 4 3
  65. 3 5 5
  66. 4 3 4
  67. 4 5 13
  68. 4 6 15
  69. 5 6 4
  70. 0 1 8 4 13 17
  71. */
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注