srcmini该算法维护了一组顶点, 这些顶点的顶点到源的最短路径是已知的。该图由其成本邻接矩阵表示, 其中成本是边缘的权重。在图的成本邻接矩阵中, 所有对角线值均为零。如果没有从源顶点Vs到任何其他顶点Vi的路径, 则用+∞表示。在此算法中, 我们假设所有权重均为正。
- 最初, 集合中没有顶点。
- 在S中包括源顶点Vs。确定从Vs到所有其他顶点的所有路径, 而无需经过任何其他顶点。
- 现在, 在最接近Vs的S中包含该顶点, 并找到通过该顶点到达所有顶点的最短路径并更新值。
- 如果图中有n个顶点, 请重复执行该步骤, 直到S中不包含n-1个顶点。
完成该过程后, 我们从源顶点获得了到所有顶点的最短路径。
示例：使用Dijkstra算法在图所示的图中找到K和L之间的最短路径。
解：
步骤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） |
由于S中包含n-1个顶点。因此, 我们找到了从K到所有其他顶点的最短距离。因此, K和L之间的最短距离为8, 最短路径为K, c, b, L。
评论前必须登录！
注册