关于狄克斯特拉算法,我主要是在《算法图解》一书中发现解释的并不清楚,所以找了博客学习,Google以后发现这篇英文博客讲解的不错,并且给出了C++,Java和C#下的代码实现。我将自己的理解用PPT做了下来,将图片放入,后文给出代码实现。

一、例子

image.png
图1. 问题
image.png
图2. 第一步+第二步
image.png
图3. 第三步+第四步
image.png
图4. 第五步+第六步
image.png
图5. 第七步+第八步

更新距离的方法: 例如上面现在更新到了顶点2,且顶点2对应的距离为中的12;且走过的邻点所以只需要更新3和8的邻点距离。

即与邻点8的距离更新为:§ 狄克斯特拉算法 - 图6; 与邻点3的邻点距离更新为§ 狄克斯特拉算法 - 图7

image.png
图6. 第九步+第十步

二、代码实现

  1. // A C++ program for Dijkstra's single source shortest path algorithm.
  2. // The program is for adjacency matrix representation of the graph.
  3. #include <limits.h>
  4. #include <stdio.h>
  5. // Number of vertices in the graph
  6. #define vertex 9
  7. // A utility function to find the vertex with minimum distance value, from
  8. // the set of vertices not yet included in shortest path tree.
  9. int minDistance(int dist[], bool sptSet[])
  10. {
  11. //Initialize min value
  12. int min = INT_MAX, minIndex;
  13. for (int v = 0; v < vertex; v++)
  14. {
  15. if (sptSet[v] == false && dist[v] <= min)
  16. {
  17. min = dist[v], minIndex = v;
  18. }
  19. }
  20. return minIndex;
  21. }
  22. // A utility function to print the constructed distance array
  23. void printSolution(int dist[])
  24. {
  25. printf("Vertex \t\t Distance from Source\n");
  26. for (int i = 0; i < vertex; i++)
  27. {
  28. printf("%d \t\t %d\n", i, dist[i]);
  29. }
  30. }
  31. // Function that implements Dijkstra's single source shortest path algorithm
  32. // for a graph represented using adjacency matrix representation.
  33. void dijkstra(int graph[vertex][vertex], int src)
  34. {
  35. int dist[vertex]; // The output array. dist[i] will hold the shortest distance from src to i
  36. bool sptSet[vertex]; // sptSet[i] will be true if vertex i is included in shortest path tree or shortest
  37. //distance from src to i is finalized.
  38. // Initialize all distance as INFINITE and sptSet[] as false.
  39. for (int i = 0; i < vertex; i++)
  40. {
  41. dist[i] = INT_MAX, sptSet[i] = false;
  42. }
  43. // Distance of source vertex from itself is always 0
  44. dist[src] = 0;
  45. // Find shortest path for all vertices
  46. for (int count = 0; count < vertex - 1; count++)
  47. {
  48. // Pick the minimum distance vertex from the set of vertices not yet processed. u is always equal to
  49. // src in the first iteration.
  50. int u = minDistance(dist, sptSet);
  51. // Mark the picked vertex as processed
  52. sptSet[u] = true;
  53. // Update dist value of the adjacent vertices of the picked vertex
  54. for (int v = 0; v < vertex; v++)
  55. {
  56. // Update dist[v] only if is not in sptSet, there is an edge fron u to v, and total weight of path
  57. // from src to v through u is smaller than current value of dist[v]
  58. if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
  59. {
  60. dist[v] = dist[u] + graph[u][v];
  61. }
  62. }
  63. }
  64. // print the constructed distance array
  65. printSolution(dist);
  66. }
  67. // driver program to test above function
  68. int main()
  69. {
  70. /* Let us create the example graph discussed above */
  71. int graph[vertex][vertex] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
  72. { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
  73. { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
  74. { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
  75. { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
  76. { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
  77. { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
  78. { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
  79. { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
  80. dijkstra(graph, 0);
  81. return 0;
  82. }

Vertex Distance from Source 0 0

1 4

2 12

3 19

4 21

5 11

6 9

7 8

8 14

可以看到和我们上面得到的结果一致。