只有五行核心的算法
假设我们有四个点。每个点之间都有一定的距离,或者甚至没有路
现在我们想要知道如何获得两点之间的最短路径
使用之前说的深度优先或者宽度优先当然是可以的,不过有没有更好的办法?
于是我们使用了Floyd-Warshall,先进了一些的算法
首先我们要知道,有的时候,通过n个点而从A->B,是有可能比直达得到更短的路径
基于这个思路,我们逐步推进
1.首先是直达,这个就不用说了
2.然后我们假设“如果允许在点1中转”,得到新的结果比较,更新数据
3.慢慢来,随后假设“如果允许在点1和点2中转”,再次更新数据
4.遍历所有可能,得到最终结果
具体怎么实现呢,我们先做一波基础操作
首先首先,我们同样用一个二维数组e来存储路径情况(其实就是图的信息)
然后是比较,以顶点1为例,可以写成:
for(i=1;i<=n,i++) { for(j=1;j<=n;j++) { if(i[e][j] > e[1][j]+e[1][j]){ e[i][j] = e[i][1]+e[1][j] //如果途径1的路程e[1][j]+e[1][j]更小 //那么把i到j的最短距离更新为e[i][j]+e[1][j]的大小 //这里实际就是比较了“当可以途径点1的时候 //路径是否能够缩短” } } }
点2,点3,点4...都是同理,于是我们使用一个循环解决这件事情:
for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j] > e[i][k]+e[k][j]) e[i][j] = e[i][k]+e[k][j];
简单粗暴的五行,包含了Floyd-Warshall算法的思想
一句话概括,Floyd-Warshall算法就是:
从i号顶点到j号顶点,只经过前k号点时,其最短路径
通过不断推进,我们最终可以得到从i到j的最短路径
#include <stdio.h> int main() { int e[10][10],k,i,j,n,m,t1,t2,t3; int inf = 99999999 ; //预设的“正无穷” //读入n和m,n表示顶点个数,m表示边的条数 //各种花里胡哨的事情的初始化 //读入图 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) e[i][j] = 0 ; else e[i][j] = inf ; //读入边 for(i=1;i<=m;i++) { scanf("%d %d %d",&t1,&t2,&t3); e[t1][t2] = t3 ; } //Floyd-Warshall算法 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j] > e[i][k]+e[k][j]) e[i][j] = e[i][k]+e[k][j]; //最终的输出 for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf("%10d",e[i][j]); } printf("\n"); } return 0 ; }
其实把9999999定义成正无穷还是挺乱挺麻烦的,而且天知道会不会有bug
于是我们还可以增加一些判断条件来改善一下情况
//Floyd-Warshall算法 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][k]<inf && e[k][j]<inf && e[i][j] > e[i][k]+e[k][j]) e[i][j] = e[i][k]+e[k][j];
Floyd-Warshall算法可以处理带有负权边的图
但是没办法处理带有“负权回路”(也叫"负权环")的图