最短路径笔记（一）：Floyd

深广度遍历所有顶点复杂度为O(n²)

Floyd最短路径时间复杂度为O(n^3)，

虽然其简洁度比其他算法简洁很多，

但是其思想实际上是不太好理解的一个，

K循环为什么在最外层，如果放在最里层会出现什么情况？

为什么能够确保取到的之前的路径是最短，如果取到的之前的路径还没有更新成最短的会怎样？

这两个问题是一个问题，还没有想清楚，有时间再研究翻翻其他资料看看

备注：Floyd算法还有一个好处就是能直接求出任意两点之间的最短路径，这是其他最短路径算法所不能的

adj=[[0,2,6,4],
     [-1,0,3,-1],
     [7,-1,0,1],
     [5,-1,12,0]]

for it in range(4):
    for jt in range(4):
        if adj[it][jt]==-1:
            adj[it][jt]=float("inf")
n=4

for k in range(n):
    for i in range(n):
        for j in range(n):
            if adj[i][j]>adj[i][k]+adj[k][j]:
                adj[i][j]=adj[i][k]+adj[k][j]
print(adj)