最短路径-Dijkstra算法

1. 问题

给定带权有向图G＝(V, E)，用Dijkstra算法求顶点a到顶点h的最短路径。

2. 解析

使用二维数组e来存储顶点之间边的关系，初始值如下：

再用一个一维数组 dis 来存储 a点到其余各个点的初始路程，我们可以称 dis 数组为“距离表”，如下：

既然是求a点到其余各个点的最短路程，那就先找一个离a点最近的点。通过数组 dis 可知当前离a点最近是b点。当选择了b点后，dis[2]的值就已经从“估计值”变为了“确定值”，即a点到b点的最短路程就是当前dis[2]值。因此，dis数组可更新为：

同理，通过4→3，可以将dis[3]的值从∞松弛为4（dis[3]初始为∞，dis[4]+e[4][3]=3+1=4，dis[3]>dis[4]+e[4][3]，因此dis[3]更新为4）。

接下去用相同的办法对e、f、g、h进行松弛，dis数组最终更新为：

3. 设计

for (v = 1; v <= n; v++)
{    
     if (e[u][v] < inf)    
     {        
          if (dis[v] > dis[u] + e[u][v])              
                dis[v] = dis[u] + e[u][v];     
     }
}  

4. 源码

https://github.com/Wang-2333/Dijkstra/blob/master/Dijkstra/Dijkstra.cpp