Day 65:弗洛伊德 - 沃肖尔(算法)
18年11月16日 · 赵晨君 573 人阅读
正文
Floyd算法是另一种在图中找到最短路径的方法。两周前我已经实现了Dijkstra的算法。但是,Dijkstra算法不适用于边缘负权重的图形。请记住,到目前为止,我们找到了一组最短的路径,任何路径扩展都会导致更长的路径。如果你有负权重,很容易找到一个反例并打破算法。
Floyd的算法即使在负权重下也能正常工作。甚至,它能够检测图中是否存在负循环。注意,具有包含顶点U,V的负循环的图在U,V之间没有最短路径。
红边权重为-1,黑边权重为1
在(0,1)之间,那条路径最短?
length(0, 1) = -1
length(0, 1, 2, 0, 1) = -2
length(0, 1, 2, 0, 1, 2, 0, 1) = -3
该算法的思想是仅使用有限的顶点集迭代地在一些顶点U和V之间建立最短路径。当这个集合被另一个顶点W扩展时,我们可以通过W获得更短的路径,或者我们已经拥有了最短的路径。
shortest(U,
V) = min( shortest(U, V), shortest(U, W) + shortest(W, V) )
你可以看到这种关系是递归的。算法中使用的迭代构造是动态编程技术的又一个展示。
算法
图像
运行1
运行2
Python3Turtle