Dijkstra的算法分析

该算法维护了一组顶点, 这些顶点的顶点到源的最短路径是已知的。该图由其成本邻接矩阵表示, 其中成本是边缘的权重。在图的成本邻接矩阵中, 所有对角线值均为零。如果没有从源顶点Vs到任何其他顶点Vi的路径, 则用+∞表示。在此算法中, 我们假设所有权重均为正。

  1. 最初, 集合中没有顶点。
  2. 在S中包括源顶点Vs。确定从Vs到所有其他顶点的所有路径, 而无需经过任何其他顶点。
  3. 现在, 在最接近Vs的S中包含该顶点, 并找到通过该顶点到达所有顶点的最短路径并更新值。
  4. 如果图中有n个顶点, 请重复执行该步骤, 直到S中不包含n-1个顶点。
完成该过程后, 我们从源顶点获得了到所有顶点的最短路径。
示例:使用Dijkstra算法在图所示的图中找到K和L之间的最短路径。
Dijkstra的算法分析 解:
步骤1:包括顶点K为S, 并确定从K到所有其他顶点的所有直接路径, 而不经过任何其他顶点。
到所有其他顶点的距离
S K a b c d L
K 0 4(K) 2(K) 20(K)
步骤2:将最接近K的顶点包含在S中, 并确定通过该顶点到所有顶点的最短路径并更新值。最接近的顶点是c。
到所有其他顶点的距离
S K a b c d L
K 0 3(K, c) 7(K, c) 2(K) 8(K, c) 18(K, c)
第三步:最接近K的顶点是9, 包含在S中。
到所有其他顶点的距离
S K a b c d L
K 0 3(K, c) 7(K, c) 2(K) 7(K, c, a) 18(K, c)
步骤4:最接近K的顶点为b, 包含在S中。
到所有其他顶点的距离
S K a b c d L
K 0 3(K, c) 7(K, c) 2(K) 7(K, c, a) 8(K, C, B)
步骤5:S中包含最接近K的顶点d。
到所有其他顶点的距离
S K a b c d L
K(c, a, b, d) 0 3(K, c) 7(K, c) 2(K) 7(K, c, a) 8(K, C, B)
【Dijkstra的算法分析】由于S中包含n-1个顶点。因此, 我们找到了从K到所有其他顶点的最短距离。因此, K和L之间的最短距离为8, 最短路径为K, c, b, L。

    推荐阅读