可以对每一个顶点使用Dijkstra算法求多源最短路。
这里我们来介绍另一种解法：Floyd
Floyd算法的主要思想是迭代。每次迭代会朝着答案更近一步。
首先定义一个二维数组Dk[i][j](k初始等于0).这个二维数组代表从i到j的最短距离。
Floyd更适合解决稠密图，所以我们使用邻接矩阵来表示图。
初始化：
如果i，j有路 D0[i][j] = G[i][j] （G为我们的邻接矩阵）
否则 D0[i][j] = INF（正无穷大）
（1）我们加入一个顶点，这个点的加入可能会影响到某两个点之间的最短路。所以检查任意i到k， k到j之间的距离。
如果 Dk-1[i][k] + Dk-1[k][j] < Dk[i][j]
更新 ：Dk[i][j] = Dk-1[i][k] + Dk-1[k][j]
（2）循环加入每一个顶点，直到所以顶点都被加入，Floyd结束。
（如果我们想得到两个点之间的路径， 在执行算法的同时记录path[i][j])
#define MaxVertexNum 100000 typedef int Vertex;
typedef struct Node
{
Vertex id;
}Node; typedef struct MyGraph
{
int g[MaxVertexNum][MaxVertexNum];
int v, e;
}MyGraph; void Floyd(MyGraph& G, int D[][], Vertex path[][])
{
//初始化
for(Vertex i = ; i < G.v; i++)
{
for(Vertex j = ; j < G.v; j++)
{
if(G.g[i][j] == -)
D[i][j] = INF;
else
D[i][j] = G.g[i][j];
}
} //迭代
for(Vertex k = ; k < G.v; k++)
{
for(Vertex i = ; i < G.v; i++)
{
for(Vertex j = ; j < G.v; j++)
{
//如果得到更小的路径，更新
if(D[i][j] > D[i][k] + D[k][j])
{
D[i][j] = D[i][k] + D[k][j];
path[i][j] = k;
}
}
}
} }