显然，对于问题：所有结点对的最短路径问题，我们需要找到图中任何两个结点间的最短路径。同时，我们能轻易得对上一章所学的Bellman_Ford或是Dijkstra算法对每个结点都调用一次而得出结果——但显然，将会浪费很多时间。
以Dijkstra算法为例，若实现它的方式为数组实现，那么Extract会搜索整个数组，消耗O(|V|)的时间——加上外层嵌套的while循环，同时处理边所用到的时间为|E|，那么算法运行的总时间为O(|V|² + |E|) = O(|V|²)。而调用 n 次，也就需要O(|V|³)的时间。
至于在图稀疏的情况下，若采用二叉堆实现：隐藏在Relax操作中的DecreaseKey、Extract_Min均消耗O(lgV)的时间，并且我们仍然只对所有的边进行一次Relax操作，因此共有|E|次DecreaseKey，|V|次Extract_Min操作；同时对原来以数组形式表示的图进行Build_Min_Heap操作会消耗O(n)时间——虽然看上去为O(nlgn)次，不过若我们更为精确地计算：每一层高度为 h 的结点，它的Max_Heapify操作并不完全等于堆的高度，而是等于它本身的高度h。这样一来，计算所有有儿子的结点处理时间的∑运算便能得出O(n)的结果。（其中高度h层的结点数目为：
，式中 n 是高度的函数，而非总元素数目，同样设最底下一层为0层）
详细的证明见书P88，在此我们仍需要把重点放在图中。
经过上述的计算，我们得到了总运行时间O((V+E)lgV)的结果，同时，至于为什么能够在从源节点出发的条件下达到O(ElgV)的结果，我目前还不清楚。猜测可能是由于当从源节点出发能够到达所有结点时，在处理完毕源节点后，对于后面的结点，在Max_Heapify中，将A[A.heapsize]换到堆的顶部时，只下渗与高度有关的次数：即下渗到同样d值为∞的层数便停止——因此，其与以上关于Build_Min_Heap的证明类似，对整体摊还分析产生的结果为O(V)，即O（V+ElgV) = O(ElgV)。同时，在的条件下，得到有O(V²）的结果。
对于我们来说，从直觉上来看，ElgV是小于V²的——但请不要忽略，E做到的是连接图中的顶点，因此它应该比V大的多——甚至在最大的情况下，会达到V!的水平。
以上是通过二叉堆进行优化，不过在此之后，还能通过斐波那契堆进行优化——由于extract_min的摊还时间为θ(lgn)，同时DecreaseKey甚至达到了Θ(1)的时间。（这个堆的实现不难，不过时间摊还分析有一定的难度）因此使用它将会使整个算法运行的时间到达O(V²lgV + VE)。
而对于包含负权重的边，将无法使用Dijkstra算法，使用Bellman_Ford，则会得到O(V²E)的运行时间。而在图稠密的情况下，甚至会到达O(V^4)的运行时间，这显然不是我们期望的结果。而在本章将使用更好的方法解决这个问题。
本章中，用来存储图信息的表示方法为邻接矩阵而非邻接链表。它满足，输入为 n x n的矩阵，其中对元素wij，当i = j时wij = 0；(i, j）存在时，存储其边的权重；当不存在时，则置为∞。
而本章中的算法输出也是一个 n x n 的矩阵，当在算法终止时，满足：
。
为解决所有节点对的最短路问题，我们不仅需要计算最短路径权重，还需要计算前驱结点矩阵，其中，当 i = j，或不存在路径时为NIL，在其他情况下给出两个结点间某条最短路径上结点 j 的前驱结点。由矩阵第 i 行诱导的子图为一棵根节点为 i 的最短路径树——它包含了从i出发到达其他所有点的最短路径上的所有前驱结点。
定义图G对于结点 i 的前驱子图Gp,i = (Vp,i, Ep, i)，其中Vp,i = {j ∈ V: pij ≠ NIL}∪{i}，Ep,i = {(pij, j): j ∈Vp, i - {i}}
以下是递归打印从 i 到 j 路径上结点的算法， 其中 i = j 时即从j回溯到了i。
Print_All_Pairs_Shortest_Path(pi, i, j)
{
if(i == j) print i;
else if pij == NIL
print "No path from i to j exists";
else Print_All_Pairs_Shortest_Path(pi, i, pij);
print j;
}其中，pi代表前驱结点矩阵， pij代表路径i到j上j的前驱结点。
一、最短路径和矩阵乘法
本节讨论解决该问题的一种动态规划算法：将进行一种类似于矩阵的乘法的操作。
最短路径的结构：
对图G＝（V，E）的所有结点对路径问题，我们有：一条路径的所有子路径都是最短路径.
现在考虑从结点 i 到结点 j 的一条最短路径p，其最多包含n - 1条边——这在前面已经证明过。同时，对于任意路径上一个点 k，其均满足：当从结点 i 到 j 为一条简单路径，那么从Vi 到 Vk，以及从Vk到Vk、Vk+1、……、Vj均为简单路径。若其不为，则我们可找到一条简单路径用于替代它。
不过，我们暂时用不到这个结论。
所有结点对最短路径的递归解：
设 为从结点 i 到结点 j 的至多包含 m 条边的任意路径的最小权重。那么 m = 0时，自然有：
i = j 时， ；而在 i 不等于 j 的条件下，其为∞。
对于 m ≥ 1， 我们需要计算的 与
的关系为：
前者为后者，以及从 i 到 j 最多由 m 条边组成的任意路径的最小权重的较小值，表达为：
其中，后面等式成立是由于：，其中
，因此实际上前者也可等价地看作包含m条边——实际上它并不包含。
同时，我们在前面提到过，对于δ(i, j)<∞，从i到j存在一最短路径——该路径也是一条简单路径，这在单源最短路径中已经证明过。简单路径中最多包含 n - 1 条边，从 i 到 j 的多于 n -1 条边的路径中，在没有负权重环路的情况下，不可能比简单路径更短，因此我们有：。
自底向上计算最短路径权重
在从 变到
的过程中，在每次都有以下过程：
Extend_Shortest_Paths(L, W)
n = L.rows
let L' be a new n * n matrix
for i = i to n
for j = 1 to n
lij' = ∞ //先进行初始化
for k = 1 to n
lij' = min(lij', lik + wkj) //尝试在所有结点中寻找i 到 j最短路径上的结点
// 以从L^(0)到L^(1)时为例，此时能在上式被min进行松弛的仅有：边(i, j)
// 因为对任何除k = i的lik，具有lik = ∞，哪怕k是i的邻边在上述的算法中，我们可以得出，L(1)是一个lij = w(i, j)的矩阵(因为 lik 在 k≠i时，必然为∞，若lij'被修改，必然由于wkj≠∞，即边(k, j)的权重不为无穷，同时要求lik也不为无穷——仅当k = i时成立，得到lij' = min(∞，0+w(i, j)) = w(i, j)
进而计算出L^(n - 1)的矩阵:
Slow_All_Pairs_Shortest_Paths(W)
n = W.rows
L(1) = W
for m = 2 to n - 1
let L(m) be a new n * n matrix
L(m) = Extend_Shortest_Paths(L(m-1), W)
return L(n-1)即为计算出的最短路径权重矩阵。
改进算法的运行时间
在解决这个问题之前，我们先回到“矩阵乘法”，观察二者有无共性：
Square_Matrix_Muliply(A, B)
n = A.rows
let C be a new n*n matrix
for i = 1 to n
for j = 1 to n
cij = 0
cij = cij + aik * bkj
return C显然的，二者都经历了新矩阵中每个点的初始化，以及根据已有的矩阵计算出新的矩阵。
在这个问题中的关键，是我们能不能把让权值矩阵等效为“被乘”。
即，虽然我们有L^(1) =Extend_Shortest_Path( L^(0), W)) = W，同时：
L^(2) = Extend_Shortest_Path(L^(1), W) = W²？
因此，我们需要对Extend_Shortest_Path算法进行观察：可以直观地看到：每一次对lij'的调整，均会涉及到对第 i 行中第k个元素怒，以及对 j 列中第k个元素，同时其也为固定的。
因此，我们可以将其结果等效于“矩阵乘法”：不过，这个“乘”并非矩阵乘法中的乘，而是相当于我们将 * 运算符重载为了对Extend_Shortest_Path的调用。
（注意：实际上，矩阵乘法也是一种乘法运算符的重载，我们不过借鉴了矩阵乘法说明其也可以进行类似的重载）
那么，我们有：
L^(1) = W
L^(2) = W * W = W²
…………
L^(n - 1) = L^(n - 2) * W = W^(n - 1)
因此，在L^(1) = W的条件下，我们可以用更为快捷的方法计算L^m，其中m ≥ n - 1：
L^(1) = W;
L^(2) = W² = L^(1) * L^(1)
L^(4) = W^4 = L^(2) * L^(2);
…………
至于为什么是大于等于，是因为显然，在上述的方法中，我们并不保证n - 1是2的整幂，同时在之前，我们已有结论：
可能有人会疑惑该算法是否成立，因为我们可能并不能保证L^(2i) = L^(i) * L^(i)。
不过，我想说，它的确成立：由于其于矩阵的相似性，我们可以将矩阵类似的说明套进来：在矩阵中，结合律亦然成立，那么对于与其类似的Extend_Shortest_Path算法也会有类似的性质。（实际的证明相当复杂，详见https://wenku.baidu.com/view/667166ef01f69e3142329410.html#）
那么我们有算法：
Faster_All_Pairs_Shortest_Paths(W)
n = W.rows
L(1) = W
m = 1
while(m < n - 1)
let L^(2m) be a new n*n matrix
L^(2m) = Extend_Shortest_Path(L(m),L(m))
m = 2m
return L^(m)