杭州交通信息网欢乐颂1安迪运动服品牌:Floyd算法的改进
来源：百度文库 编辑：杭州交通信息网 时间：2024/05/06 02:49:58
给出一个图，求最短路径问题的一个O(n^3)算法
优点：容易理解，可以算出任意两个节点之间最短距离的算法，程序容易写
缺点：复杂度达到三次方，不适合计算大量数据
Floyd算法的功能是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵.
它的功能看上去挺强大的,但它的实现却很简单,和Washall算法很相似,也是一个三层循环,思路也是相似是,就是利用前面计算的结果:
核心思想：设立[i,j]为权值
for(k=0;k<len;k++)
for(i=0;i<len;i++)
for(j=0;j<len;j++)
if(a[k,j]+a[j,i]<a[k][i])a[k][i]=a[k,j]+a[j,i];
开一个数组（len*len)当b[i,j]=1 是则为这两点联通，我想在Floyd算法判断前先判断要处理的点是否联通，应该怎么作。。
希望能够给出基本实现代码,Pascal和C
优点：容易理解，可以算出任意两个节点之间最短距离的算法，程序容易写
缺点：复杂度达到三次方，不适合计算大量数据
Floyd算法的功能是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵.
它的功能看上去挺强大的,但它的实现却很简单,和Washall算法很相似,也是一个三层循环,思路也是相似是,就是利用前面计算的结果:
核心思想：设立[i,j]为权值
for(k=0;k<len;k++)
for(i=0;i<len;i++)
for(j=0;j<len;j++)
if(a[k,j]+a[j,i]<a[k][i])a[k][i]=a[k,j]+a[j,i];
开一个数组（len*len)当b[i,j]=1 是则为这两点联通，我想在Floyd算法判断前先判断要处理的点是否联通，应该怎么作。。
希望能够给出基本实现代码,Pascal和C
判断连通可以在输入时作一下预处理
Floyd已经是DP的思想了.
可以有些小优化.但求一个图中任意两点的最短路径目前只有o(n^3)的算法