【文件属性】：
文件名称：最短路算法-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2021-06-09 22:35:00
集训队论文集
4.1 最短路算法
建立带权有向图G′ = (V, E′)：
• 对于图G中原有的边(u, v) ∈ E，在图G′中连上从点u到点v权值为0的边；
• 若第i次操作加入边(xi, yi)，则在图G′中连上从点xi到点yi权值为i的边。
定义 4.1. 若图G′中存在一条从点i到点 j的路径，且途径边的权值均小于等于w，则h(w)i, j = 1，
否则h(w)i, j = 0。
定义 4.2. gi, j = min{w | h
(w)
i, j = 1}.
推论 4.1. 第gi, j次操作之后，图G中就存在了一条从点i到点 j的路径。
若能对所有点对i, j求出gi, j，就能得到每次操作后的传递闭包了。
观察发现，这个问题等价于求所有点对间的最短路。使用Floyd-Warshall算法，时间复
杂度为O(n3)。使用Dijkstra算法配合斐波那契堆优化 [4] ，时间复杂度为O(n2 log n + n(m +
q))。
值得注意的是，该算法是离线的。
4.2 对Floyd-Warshall算法的拓展
Floyd-Warshall算法求解传递闭包的本质，就是动态地加入“中转点”来更新传递闭包。
事实上，中转点加入图中的顺序并不一定得是1,2,...,n，它其实可以将所有点以任意的顺序
加入图中。这一优美的性质，使得它能在一定程度上支持动态问题。
通过下面这个例子来更好地理解它的应用。
79