All‐Pair Shortest Path - rFronteddu/general_wiki GitHub Wiki
All-pairs shortest paths is the problem of finding shortest paths between all pair of vertices in a graph. We typically want the result in a tabular format: the entry in u's row and v's column should be the weight of a shortest path from u to v.
We can solve this problem by running s-ss-p algorithm |V| times, one for each vertex as the source.
We will show how we can do better and the relationship of the all-pairs shortest-paths problem to matrix multiplication and study its algebraic structure.
Most of the algorithm in this section assume an adjacency matrix representation. For convenience, we assume the that vertices are numbered 1, 2, ..., |V|, so that the input is an n x n matrix W representing the edge weights of an n-vertex directed graph G =(V,E). That is, $W = w_{ij}$ where $w_{ij}$ = 0 if i==j, MAX_VALUE if i!=j and there is no edge connecting the two and the weight of the directed edge (i,j) otherwise.
For now we assume no negative-weight cycles.
The tabular output of this algorithm is an n x n matrix D = $(d_{ij})$ where each entry contains the weight of a shortest path from vertex i to vertex j (which at termination is the shortest path $\delta (i,j)$.
To solve this problem we compute the shortest-path weights but also a predecessor matrix P = $(p_{i,j})$ where an entry is nil if i==j or there is no path from i to j., otherwise it is the predecessor of j on some shortest path from i.
For each vertex i $\in$ V we define the predecessor subgraph of G for i as $G_{p,i}=(V_{p,i},E_{p,i})$ where V_{p,i} are all the vertices in $P_{ij}$ including i and $E_{p,i}$ are all the edges in $V_{p,i}$ that go from $P_{ii}$ to j excluding i.
Print-APSP(P, i, j)
if i == j
print i
else if P[i,j] == nil
print "no path from" i "to" j "exists"
else Print-APSP(P, i, P[i,j])
print j