Floyd-Warshall
Floyd算法，是一种著名的多源最短路算法。
核心思想：
用邻接矩阵存储图，核心代码为三重循环，第一层枚举中间点k，二三层分别枚举起始点i与目标点j。然后判断经过中间点k后，i与j间的路程是否会减小。如果是，就更新i，j之间的最短路。
for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j];
需要注意的是，为了保证更新成功，需要将e数组初始化为无穷大。同时为了防止程序做无意义的到自己的最短路，将每个节点到本身的距离初始化为0。
算法复杂度：
该算法的空间复杂度为n^2(不算优秀，但勉强接受),时间复杂度O(n^3)（呵呵）。
完整代码：
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int inf=99999999;
int n,m,x,y,z,s;
int dis[1001][1001];
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j) dis[i][j]=inf;
else dis[i][j]=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
dis[x][y]=dis[y][x]=z;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[i][k]+dis[k][j];
for(int i=1;i<=n;i++)
printf("%d ",dis[s][i]);
return 0;
}
算法优化：
for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]), dis[j][i] = dis[i][j];
这里利用了矩阵的对称性，只更新一半矩阵即可。但整体时间复杂度还是不够理想，依然是O(n^3)。所以通常n较大时不考虑此算法。