如果有一张图，我希望获得从每一个点到其他另外的所有点的距离的之和，那么你该怎么做呢？
下面这个 Floyd 算法就非常适用
Floyd
Floyd 采用了动态规划的思想，来解决一个有向图 $G=(V,E)$ 上每一对顶点间的最短路径问题。它允许权值为负数。
对于任意一对顶点 $i$ 和 $j$ ($i,j \in V$)，观察从 $i$ 到 $j$ 且经过中间顶点的最短路径，设 $p$ 为其中的一条最小值路径，Floyd 就是利用了路径 $p$ 与 $i$ 到 $j$ 之间的最短路径之间的联系。这一联系依赖于 $k$ 是否是路径 $p$ 中的中间点。
其实我们就对于每一个点的距离 $d[ij]$ 规定如下：
$$d[ij] = \left\{ \begin{array}{rcl}0&i=j\\w(i,j)&i到j存在边\\INF&i到j不存在边\end{array}\right.$$
在动态规划更新时，每一个点的距离 $d[ij]$ 是
$$d[ij] = \min(d[ij], d[ik] + d[kj])$$
实现
基于上面这个式子，我们在用一个循环来寻找中间点，然后再用两层循环来动态规划 $i,j$ 。然后里面根据第一个公式写出动态方程。
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)
{
if (i == j)
d[i][j] = 0;
else if (w[i][j])
d[i][j] = w[i][j];
else
d[i][j] = INF;
}
}
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);其中 w 是一个邻接矩阵数组。d[i][j] 是表示从 $i$ 到 $j$ 的最短距离。
时间复杂度
考虑使用任何一个算法都需要计算它的时间复杂度，否则超时你都不知道咋回事。
执行一次三重循环内部的动态转移方程的时间复杂度是 $O(1)$ ，三重循环是从 $1$ 到 $n$ 的，所以整个的时间复杂度就是 $O(n^3)$ 。所以如果题目的 $n$ 特别大，我们还是选用做好多次 Dijkstra 吧。