通过多重图理解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的最短路径。