Floyd- Warshall算法：
这个算法就是让我们去寻找从点i到点j的距离，有以下两种情况：
（1）. 两点直接到达的距离最短。
（2）. 两点之间通过1个或者1个以上节点连接到达的距离最短。
其中主要代码只有五行，通过不同的点去中转看看中转之后的点到达的距离与直接到达是否小，如果小就更新距离。
#include<stdio.h> int main() { int e[10][10],k,i,j,n,m,t1,t2,t3; int inf=999999;//定义认为为正无穷大 scanf("%d%d",&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; } //主要算法 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][i]<inf&&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; }
Dijkstra算法:
这个算法就是找到一个顶点，然后看看这个顶点到其他点的最小距离。如果到下一个顶点的距离比当前顶点大，九成新更新距离。
具体步骤：
1、将所有顶点分为两部分：已知最短距离路程的顶点集合P和未知最短路径的顶点集合Q。最开始，已知最短路径的顶点集合P只有一个顶点。我们这里用一个book记录那些点已经在集合P中。
2、设置源点s到自己的距离为0，若有源点能直接到达顶点，则距离为e[s][i],若不能到达此时距离为无穷大，这个我们定义99999999为无穷大。
3、在集合Q的所有顶点中选择离源点s最近的顶点u加入集合P中，并考察以u为起点的边，对每一条边进行松弛。
4、重复第3步，直到集合Q为空。
#include<stdio.h> int main() { int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,min; int inf=99999999;//无穷大 scanf("%d%d",&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; } //初始化dis数组，这个是从1到其他顶点初始化 for(i=1;i<=n;i++) dis[i]=e[1][i]; //book初始化 for(i=1;i<=n;i++) book[i]=0; book[1]=1; //算法核心 for(i=1;i<=n-1;i++) { min=inf; //找到离1号顶点最近的点 for(j=1;j<=n;j++) { if(book[j]==0&&dis[j]<min) { min=dis[j]; u=j; } } book[u]=1; for(v=1;v<=n;v++) { if(e[u][v]<inf) { if(dis[v]>dis[u]+e[u][v]) dis[v]=dis[u]+e[u][v]; } } } for(i=1;i<=n;i++) printf("%d ",dis[i]); return 0; }
