turtle Floyd-Warshall(Graph)

import turtle
turtle.speed(0)
size=1
while size < 500:
  turtle.forward(size)
  turtle.right(1000)
  size = size + 1
turtle.done()

最短路径算法

Floyd-Warshall（打开新窗口）的算法是用来寻找具有正负边权重的加权图中的最短路径。该算法的一次执行就能找到所有对顶点之间最短路径的长度（权重之和）。只要稍加改动，它就能打印出最短路径，并能检测出图中的负循环。Floyd-Warshall是一种动态编程算法。

让我们看一个例子。我们将在这个图上应用Floyd-Warshall的算法：图例

image.png

我们做的第一件事是，我们取两个二维矩阵。这些是邻接矩阵（打开新窗口）

矩阵的大小将是顶点的总数。对于我们的图形，我们将采取4*4矩阵。距离矩阵将存储迄今为止在两个顶点之间发现的最小距离。

首先，对于边，如果u-v之间有一条边，并且距离/权重是w，我们将存储：distance[u][v] = w。对于所有不存在的边，我们将输入无穷大。

路径矩阵是为了重新生成两个顶点之间的最小距离路径。因此，最初，如果u和v之间有一条路径，我们就把path[u][v]=u放进去。这意味着从顶点u到达顶点v的最佳方式是使用连接v和u的边。我们的图的两个表将看起来像。

因为没有循环，所以对角线设为N，而与顶点本身的距离为0。

为了应用Floyd-Warshall算法，我们要选择一个中间的顶点k。然后对于每个顶点i，我们要检查是否可以从i到k，再从k到j，其中j是另一个顶点，并使从i到j的成本最小化。

如果当前距离[i][j]大于距离[i][k]+距离[k][j]，我们要把距离[i][j]等同于这两个距离的总和。

而path[i][j]将被设置为path[k][j]，因为最好是从i到k，然后再从k到j，所有顶点将被选为k。 我们将有3个嵌套循环：对于k从1到4，i从1到4，j从1到4。

if distance[i][j] > distance[i][k] + distance[k][j]
    distance[i][j] := distance[i][k] + distance[k][j]
    path[i][j] := path[k][j]
end if

所以我们基本上要检查的是，对于每一对顶点，我们是否通过另一个顶点获得更短的距离？我们的图的总操作数将是444=64。这意味着我们要做64次这样的检查。让我们看一下其中的几个。

当k=1，i=2，j=3时，distance[i][j]为-2，不大于distance[i][k]+distance[k][j]=-2+0=-2。 所以它将保持不变。

同样，当k=1，i=4，j=2时，distance[i][j]=无穷大，这大于distance[i][k]+distance[k][j]=1+3=4。所以我们把distance[i][j]=4，并把path[i][j]=path[k][j]=1。

这意味着，从顶点4到顶点2，路径4->1->2比现有路径短。这就是我们填充两个矩阵的方法。这里显示了每一步的计算过程（打开新窗口）。进行必要的修改后，我们的矩阵将看起来像。

image.png

这就是我们的最短距离矩阵。例如，从1到4的最短距离是3，从4到3的最短距离是2。 我们的伪代码将是。

Procedure Floyd-Warshall(Graph):
for k from 1 to V     // V denotes the number of vertex
    for i from 1 to V
       for j from 1 to V
           if distance[i][j] > distance[i][k] + distance[k][j]
               distance[i][j] := distance[i][k] + distance[k][j]
               path[i][j] := path[k][j]
           end if
       end for
    end for
end for

输出路径:

为了打印路径，我们将检查路径矩阵。为了打印从u到v的路径，我们将从path[u][v]开始。我们将不断改变v=path[u][v]，直到找到path[u][v]=u，并将path[u][v]的每个值推到堆栈中。找到u后，我们将打印u，并开始从堆栈中弹出项目并打印它们。这是因为路径矩阵存储了从任何其他节点到v的最短路径的顶点的值。伪代码将是。

Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
    S.push(Path[source][destination])
    destination := Path[source][destination]
end while
print -> source
while S is not empty
    print -> S.pop
end while

寻找负的边缘循环

为了找出是否有一个负的边缘循环，我们需要检查距离矩阵的主对角线。如果对角线上的任何数值是负的，那就意味着图中有一个负的循环。

复杂度

Floyd-Warshall算法的复杂度为O(V³)，空间复杂度为。O(V²)。