文件名称：最短路算法-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2024-06-29 16:21:40
集训队论文集
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