数据结构-图（三）-最短路径之Dijkstra

朱雀 2022-06-04 06:50 200阅读 0赞

Dijkstra算法用于解决单源最短路径问题，即，从一个节点出发，计算该结点到图中其他节点的最短距离。

**算法思想：**

Dijsktra提出了一个按路径长度递增的顺序逐步产生最短路径的算法。设置两个结点集合S、T，分别存储已经找到最短路径的节点和还未找到最短路径的结点。初始时，S中只有其实结点v，然后从T中寻找到v的路径长度最短的结点，将此点加入S。每次有新的结点u加入S后都需要更新T中节点到v的路径距离，路径距离的值是“原来的当前最短路径长度值”和“从源点经过节点u到该结点 的路径长度”中的较小者。其中，从源点经过节点u到该结点 的路径长度=节点u到源节点的最短路径长度+u到待更新结点的边权值。重复，直到T中所有结点全部加入到集合S中。

示例：

> 参考：[https://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html][https_www.cnblogs.com_biyeymyhjob_archive_2012_07_31_2615833.html]

![这里写图片描述][SouthEast]

计算A到其他所有节点的最短距离，表中红色节点表示S中结点，黑色表示T中节点。

1、初始时，与A邻接的点的最短路径距离为其与A之间边的权重，不邻接的点到A的距离计为无穷

<table> 
 <thead> 
  <tr> 
   <th>结点</th> 
   <th align="left"><font>A</font></th> 
   <th align="left">B</th> 
   <th>C</th> 
   <th>D</th> 
   <th>E</th> 
   <th>F</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>到源点的最短路径距离</td> 
   <td align="left"></td> 
   <td align="left">6</td> 
   <td>3</td> 
   <td>–</td> 
   <td>–</td> 
   <td>–</td> 
  </tr> 
 </tbody> 
</table>

2、 寻找T中到v的最短路径距离最短的结点，加入s（此例中为C），此时该结点对应的最短路径距离就是该节点到源节点的最终最短距离。  
3、更新其余节点到源节点的最短路径距离，dis=min\{当前最短路径距离，经过2中加入S的结点再到源节点的路径距离\}

4、重复2-3

> 选择所有未被访问结点中到源节点最短路径距离最短的结点B加入S，更新在允许经过节点B的情况下其余结点到源节点的最短路径距离）

> 选择所有未被访问结点中到源节点最短路径距离最短的结点D加入S，更新在允许经过节点D的情况下其余结点到源节点的最短路径距离

> 选择所有未被访问结点中到源节点最短路径距离最短的结点E加入S，更新在允许经过节点E的情况下其余结点到源节点的最短路径距离

> 选择所有未被访问结点中到源节点最短路径距离最短的结点F加入S，此时T为空，结束循环

[https_www.cnblogs.com_biyeymyhjob_archive_2012_07_31_2615833.html]: https://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html
[SouthEast]: /images/20220604/9374157fc4cb433da984999f37fa9c6a.png