最短路是图论的基础部分。其中学过4个主要算法，分别是Floyed，Dijkstra，Ford，SPFA。SPFA作为Ford的队列实现，有一定的优化，因此就不说Ford了。
首先两点间距离读取都是一样的。
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;++i) f[i][i]=0;
for(int i=1;i<=e;++i)
{
scanf("%d%d%d",&a,&b,&distance);
f[a][b]=distance;
f[b][a]=distance;
}
Floyed。特点是解决了所有点的最短路，且试用于负边权的情况。但时间复杂度是O(n^3)，所以一般用处不大。
#define FOR(i,x,y) for(int i=x;i<=y;++i) #define MIN(a,b) a<b?a:b FOR(k,1,n) FOR(i,1,n) FOR(j,1,n) f[i][j]=MIN(f[i][j],f[i][k]+f[k][j]);
Dijkstra。特点是计算了单点间最短路，不能在负边权的时候使用。时间复杂度O(n^2)，可以考虑使用。
int Dijkstra(int st,int en)
{
memset(vis,0,sizeof(vis));
FOR(i,1,n) ans[i]=f[st][i];
FOR(i,1,n)
{
minn=0x3f3f3f3f; k=-1;
FOR(j,1,n) if(!vis[j]&&ans[j]<minn)
{
minn=ans[j];
k=j;
}
if(k==-1) break;
vis[k]=true;
FOR(j,1,n) ans[j]=MIN(ans[j],ans[k]+f[k][j]);
}
return ans[en];
}
SPFA。特点是计算单点间最短路，可以计算负边权最短路，不能直接算负边权回路。时间复杂度O(E)，优先推荐使用。
原文：http://www.cnblogs.com/cons/p/5187282.html