Floyd-Warshall——只有五行的算法
求任意两个点之间的最短路程。 从i号顶点到j号顶点只经过前k号顶点的最短路程，这是一种动态规划的思想。
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];n个顶点，m条边，接下来的m行每一行有3个数，顶点u，v以及他们之间的距离 l。 #include<iostream> using namespace std; int e[111][111]; int n,m,u,v,l; const int inf=999999; void init() { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) e[i][j]=0; else e[i][j]=inf; } } } void floyd() { int i,j,k; 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]; } } } } int main() { int i,j; cin>>n>>m; init(); //读入边 for(i=1;i<=m;i++) { cin>>u>>v>>l; e[u][v]=l; } floyd(); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cout<<e[i][j]<<endl; } } return 0; }
Dijkstra算法 ——单源最短路径
每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。
1.把所有的顶点分为两部分：已知最短路程的顶点集合P和未知最短路径的顶点集合Q。 最开始，P集合中只有源点一个顶点，用visit[i]数组来记录哪些点在集合P。visit[i]=1表示这个顶点在P集合中，visit[i]=0表示这个顶点在Q集合中。
2.设置源点s到自己的最短路径为0，即dis[s]=0,若存在有源点能直接到达的顶点i，则把dis[i]设为e[s][i],同时把所有其他（源点不能到达的）顶点的最短路径设为inf。
3.在集合Q的所有顶点中选择一个离源点s最近的顶点u（dis[u]最小）加入到集合P，并考察所有以点u为起点的边，对每条边进行松弛操作。例如:存在一条u到v的边，通过u->v添加到尾部来拓展一条从s到v的路径，这条路径的长度是dis[u]+e[u][v]。如果它的值比目前已知的dis[v]的值要小，我们可以用新值来替代当前dis[v]中的值。
4.重复第3步，如果集合Q为空，算法结束，最终dis数组中的值就是源点到所有顶点的最短路径。
代码实现如下：
#include<iostream> using namespace std; int e[111][111],dis[111],visit[111]; int n,m; const int inf=999999; void init1() { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) e[i][j]=0; else e[i][j]=inf; } } } void init2() { //初始化dis数组，1号顶点到其余各个顶点的初始距离 for(int i=1;i<=n;i++) { dis[i]=e[1][i]; } //初始化visit数组 for(int i=1;i<=n;i++) { visit[i]=0; } visit[1]=1; } void dijkstra() { int i,j,u,v,min; for(i=1;i<=n-1;i++) { //找离1号顶点最近的顶点 min=inf; for(j=1;j<=n;j++) { if(visit[j]==0&&dis[j]<min) { min=dis[j]; u=j; } } visit[u]=1; for(v=1;v<=n;v++) { if(e[u][v]<inf) { if(visit[v]==0&&dis[v]>dis[u]+e[u][v]) dis[v]=dis[u]+e[u][v]; } } } } int main() { int i,j,t1,t2,t3; cin>>n>>m; init1(); //读入边 for(i=1;i<=m;i++) { cin>>t1>>t2>>t3; e[t1][t2]=t3; } init2(); dijkstra(); for(i=1;i<=n;i++) { cout<<dis[i]<<endl; } return 0; }