The all-pairs shortest-paths problem (APSP) is to find a shortest path from u to v for every pair of vertices u and v in V
Approaches to solving APSP:
- Run a single-source shortest paths algorithm starting at each vertex v ∈ V .
- Use the Floyd-Warshall algorithm or other algorithms (matrix-based methods), which will be introduced in this lecture.
Floyd-Warshall algorithm
This uses dynamic programming in a different manner.
原理：通过遍历除了A,B两个点之外的所有点（D），判断weight(A,B) < weight(A,D) + weight(D,B):
if true 就refresh，else 继续遍历。
这里的A,B就是指所以的pairs in graph.
数据结构: 2 matrix store the distance between each nodes. （利用前一个matrix 来形成后一个matrix）
初始化：matrix_1 stores all the known distance between every node.
d(x,y) =
x = y => 0,
x and y are not connected => infinite,
x and y are connected => weight of the connected edge.
根据原理，可以得到核心程序：
# K is all the nodes we have to go through.
for k in range(0,n):
# X is the x-coordinate in matrix_1
for x in range(0,n):
# Y is the y-coordinate in matrix_1
for y in range (0, n):
if weight(x,y) > weight(x,k) + weight(k,y):
push weight(x,k) + weight(k,y) into the value of (x , y) in matrix_2
else：
push weight(x,y) into the value of (x , y) in matrix_2
以上程序只能得到最短路程，无法记录路径，我们还需要在每次refresh的时候push这个中转node 到路径数组即可。
Time complexity: O(V**3)
