1，核心思路：
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
其状态转移方程：map[i,j]=min{map[i,k]+map[k,j],map[i.j]} map[i,j]表示i到j的最短距离，k是穷举i,j的断点。
2，算法流程：
1，把图用邻接矩阵G表示出来，如果从Vi 到Vj 有路可达，则G[i,j]=d,d表示该路的长度，否则G[i,j]=最大值。
2，遍历这个矩阵，G[i,j]=min(G[i,j],G[i,k]+G[k,j]);
3，核心代码：
for(k=1;k<=n;k++) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(G[i,j]>G[i,k]+G[k,j]) G[i,j]=G[i,k]+G[k,j]; } } }
4，优缺点：
优点：Floyd 算法适用于稠密图，简单有效，容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。
缺点：时间复杂度比较高，不适合计算大量数据。
5，
时间复杂度：O(n^3)
空间复杂度：O(n^2）
举例一个练习题目：http://acm.hdu.edu.cn/showproblem.php?pid=1690
这个题目最关键的地方就是构图，因为数据较小，所以O(n^3)不会超时。构图的时候比较麻烦，没有什么大的技术含量，贴一下代码。
#include<stdio.h> #define INF 100000000000 #define MAXN 150 __int64 L[5],C[5]; __int64 map[MAXN][MAXN],X[MAXN]; int n,m; void Input_Deal() { int i,j; for(i=1;i<=4;i++) scanf("%I64d",&L[i]); for(i=1;i<=4;i++) scanf("%I64d",&C[i]); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%I64d",&X[i]);//输入部分 for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(i==j) map[i][j]=0; else map[i][j]=INF; } for(i=1;i<=n;i++) { map[i][i]=0; for(j=i+1;j<=n;j++) { __int64 distance=X[j]-X[i]; if(distance<0) distance=-distance; if(distance>L[4]) map[i][j]=map[j][i]=INF; else if(distance>L[3]) map[i][j]=map[j][i]=C[4]; else if(distance>L[2]) map[i][j]=map[j][i]=C[3]; else if(distance>L[1]) map[i][j]=map[j][i]=C[2]; else if(distance>0) map[i][j]=map[j][i]=C[1]; }//构图部分 } } void Floyd(int n) { int i,j,k; for(k=1;k<=n;k++){ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(map[i][j]>map[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j]; } } }//利用floyd找最少花费 } int main() { int t,ca=1,i; scanf("%d",&t); while(t--) { Input_Deal(); Floyd(n); printf("Case %d:/n",ca++); for(i=1;i<=m;i++) { __int64 start,aim; scanf("%I64d%I64d",&start,&aim); if(map[start][aim]==INF) { printf("Station %I64d and station %I64d are not attainable./n",start,aim); } else printf("The minimum cost between station %I64d and station %I64d is %I64d./n",start,aim,map[start][aim]); } } return 0; }