图1
关于这个算法的个人理解(---下图都代表箭头→)
关于这个算法其实就是寻找最短路径，笔者是根据代码和图形来理解核心思想
关键点：如图中，v1→v2 权重为4，我们需要遍历v1去往每个点然后经历过某个点去往或者经历多个点去往v2的路径
可以代表为d[i][j]>d[i][k]+d[k][j] 此处的i j k我在此解释（个人想法）一下，许多人就是卡在这里不太理解。
其实这里套用了一个三层循环，可以理解为，图1中，v0→v1>v0→v0+v0+v1
k是最外层循环++，因为我们需要找，从v0出发，然后去往图中每一个顶点的路径，然后会经过v0点的最短路径，并且记录下来然后修正权重
i代表第二曾循环++，从k取值0开始，就从v0开始取每行的值，然后去j，取对应的列的值，是列列列！！！，
到这里，Ijk 就知道是干嘛的了，只要当，我们选择i去往j这个点的时候，经过k这个点 如果权重会小，则把i去往j这个路径修正为最小的点即
d[i][k]+d[k][j],并且记录下来我们曾经修改过的点。一直循环完，这里的算法时间是n的三次方.
至于路径数组是干嘛的，我们需要知道，是如何经过哪些点，获得最小路径的
因为我们生成路径数组的时候，是对应的下标生成的二维数组的值，看图1
注意观察（重点）路径数组的每个下标值必定等于该列的值，v0 = 0 v1 = 1
有了这个以后，我们只需要判断当前取出来的值是否等于该列的值，如果等于就代表经过了这个点，才走的最短路径
否则没有经过。
这个算法其实不难，核心点在于去往每个点我们所要经历的每个点。并且记录下来 很重要
网友评论