数据结构(6.4_4)——Floyd算法
Floyd算法
第一步：建立两个二维数组，一个用来存放所有顶点，一个用来存放顶点之间的中转点
第二步：循环遍历A矩阵，若,则
，
；否则
和
保持原值，循环完所有i，j后更新数组并且k+1
第三步：重复第二步操作
初始：
第0轮：
第一轮：
第二轮：
总：
代码实现：
时间复杂度和空间复杂度：
Floyd算法实例
1、
v0;
v1；
v2；
v3；
v4;
循环后无顶点需要更新
寻找最短路径
寻找v0——v4
练习：Floyd算法用于负权图
不能解决的问题
总结：
