37.2° Blog

1.解决的问题

求解单源最短路径，但不适用于有负权值的带权图。

2.算法思想

1. 集合T中存放已求得最短路径的顶点；
2. 集合U中存放待求最短路径的顶点；
3. 每次从集合U中取出一个起始点Vs（源点）到其路径长度最小的一个顶点Vr加入到集合T中；
4. 更新Vr所有邻接顶点Vk到Vs的路径长度；
5. 重复2，3步骤，直到集合U为空。

3.伪代码

将源点Vs加入到集合T;    // T的初始化
将源点Vs到各个顶点Vj的路径长度初始化为无穷大;
while U不为空
{
  从U中取距离源点Vs路径最短的顶点Vr加入集合T;
  获得Vs到Vr的路径Vs->...->Vr及其路径长度，该路径为Vs到Vr的最短路径;
  获取Vr的每个邻接顶点Vk，更新Vs到Vk的路径，操作如下：
  if (Vs到Vr的路径长度 Dsr+d<r,k> 小于 Dsk)
  {
    // 更新Vs到Vk的路径长度
    Dsk = Dsr+d<r,k>;
  }
  从U中删除顶点Vr;
}

4.手算示例

对图G进行顶点3到其余顶点的最短路径

初始化：将源点3加入到集合T中，其他顶点加入集合U中

路径终点	初始化	第一趟	第二趟	第三趟	第四趟	第五趟
1	7 3→1	7 3→1	7 3→1
2	∞	∞	10 3→5→2	10 3→5→2
3	0	0	0	0	0	0
4	∞	∞	∞	47 3→1→4	22 3→5→2→4	22 3→5→2→4
5	6 3→5	6 3→5
6	∞	∞	14 3→5→6	14 3→5→6	14 3→5→6
选择的顶点	3	5	1	2	6	4
T	{3}	{3,5}	{3,5,1}	{3,5,1,2}	{3,5,1,2,6}	{3,5,1,2,6,4}
U	{1,2,4,5,6}	{1,2,4,6}	{2,4,6}	{4,6}	{4}	{}