先说一下我觉的比较简单的一个吧，至少看起来是很简单也比较容易理解，就是Floyd算法。该算法是用来求多源最短路的算法，也就是说，求图中任意两个点之间的最短路。
他的主要思想就是初始状态是所要求最短路的起点和中点，然后不停地将其他点往这两个顶点之间加。
首先要用一中数据结构来存储图吧，一般来讲还是用邻接矩阵。m[i][j]表示由i到j的最短路。当i==j的时候赋为0，如果两点之间没有弧，初始化为无穷大。
对于算法地理解，是一个由最简单地情况推到一般的情况的。假设，现在要求i到j的最短路径，先考虑只把1顶点加入i j 之间，那么由图存储的任意两点之间的最短路会有所更新。然后再在邻接矩阵更新了的前提下，考虑只有12两个顶点加入ij之间的情况，再更新邻接矩阵中存储的最短路径的值。这样一来，每次都考虑比上一次多一个的顶点加入ij之间，直到所有顶点都考虑完毕。
如果还是看不懂，可以自己画一个邻接矩阵来模拟一下最短路的更新过程。
下面贴一下代码：
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; int main() { int a,b,s; int n,m;//n个顶点，m条路径 cin>>n>>m; int ma[1005][1005];//定义邻接矩阵存储最短路 for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(i==j) { ma[i][j]=0; } else { ma[i][j]=INF; } } } for(int i=0; i<m; i++) { cin>>a>>b>>s; ma[a][b]=s; } /*下面是算法的核心部分了*/ for(int k=1; k<=n; k++) //k就是每次加入ij之间的顶点 for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) //循环求每两个顶点之间的最短路 { if(ma[i][k]+ma[k][j]<=ma[i][j]) ma[i][j]=ma[i][k]+ma[k][j];//如果加入顶点能是最短路变短，更新 } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { printf("%d ",ma[i][j]); } printf("\n"); } return 0; } 参考博客：http://developer.51cto.com/art/201403/433874.htm
