通过多重图理解Dijkstra
多重图
图分为简单图与多重图，其区别就在于，简单图没有自环与平行边，而多重图有。我们通常讨论的是简单图，但实际上通过多重图能更好的理解Dikjstra算法。
Dijkstra算法
让我们回顾一下Dijkstra算法。
Dijkstra算法维护两个集合S，T。S为已求出最短路径的点集，而T为未求出最短路径的点集。初始状态下，S仅含有起始点；此后，每次从T中选出距离S最近的点加入S。往复下去，直到目标点加入S或者没有点可以加入S。
如果我们从多重图的角度看。可以把集合S理解为一个点，该点到其余点存在平行边。如下图，S点到外点1有3条平行边。
这样，点与点的距离，可以定义为两点间所有平行边的最小长度。有了多重图中点与点距离的定义，上图就可以等价成这样(这里我加上了距离)
通过定义距离，多重图又转化回简单图，但不同的时，我们把含有多个点的点集等价为了一个点S。我们很容易可以求出，(S,e1)这条边一定会在S到e1的最短路径上，故可以把e1加入S中，同时更新距离。
通过多重图的距离定义，不断将多重图转化为简单图，再通过递推公式，就是dijkstra算法的思路了。
递推公式
Dijkstra的递推公式就是，
1、在简单图中，与v0距离最近的点v1，则v0到v1的最短路径是(v0,v1)；
2、在简单图中，v0到vt的最短路径的p1，vt到v1的最短路径是p2，则 为v0到v1的最短路径。