Shortest paths from and to all vertices
This functionality does not run in MATLAB.
Graph::shortestPathAllPairs(G
, <SearchFor = Weights  Costs
>)
Graph::shortestPathAllPairs(G)
returns a
table with all paths between all vertices.
Graph::shortestPathAllPairs(G, SearchFor=Costs)
returns
a table
with all paths according to the edge costs.
Graph::shortestPathAllPairs(G, SearchFor=Weights)
returns
a table
with all paths according to the edge weights.
(Default)
A small graph to be used for the algorithms:
G := Graph([a, b, c, d], [[a, b], [a, c], [b, c], [c, d]], EdgeWeights = [2, 1, 3, 2], EdgeCosts = [1, 3,1, 2], Directed):
Now the shortest path between all vertices is found according to the edge weights, because no specification was given and defaults are used.
Graph::shortestPathAllPairs(G)
The interpretation of the table is as follows:
The first table holds each path: (FromVertex, ToVertex) = weight/cost.
The second table is a bit more tricky. The left hand side again is
the path itself. On the right hand side though, the vertex that was
found before the final vertex was reached is stated. If for example
the path from a
to d
is to be
found with all vertices that are used within this path it is done
in the following way: First take the path itself (a, d)
.
The predecessor is c
. Now have a look for the path (a,
c)
. It's predecessor is a
. Since the
predecessor equals the first vertex in the path to be found, the search
is over and the path a > c > d
is found.
To search the graph for costs the option SearchFor=Costs
has
to be added.
Graph::shortestPathAllPairs(G, SearchFor = Costs)
Now the weights of the graph are changed, so that negative edge weights are assigned. You will see that this does not influence the correctness of the results the algorithm returns (like for example Dijkstra).
G := Graph([a, b, c, d], [[a, b], [a, c], [b, c], [c, d]], EdgeWeights = [2, 1, 3, 2], EdgeCosts = [1, 3,1, 2], Directed):
G := Graph::setEdgeWeights(G, Graph::getEdges(G), [2, 1, 3, 2]):
Graph::shortestPathAllPairs(G)

Graph 

Defines whether the weights of the graph are considered or the
costs. Default is 
List consisting of two tables. The first table holds the sum of the path weights or costs and the second the predecessors for every path (to find the complete path).
The algorithm is also known as FloydWarshall or RoyWarshall algorithm. The idea behind it is to solve the problem by continuous matrix multiplication. he only difference is that Floyd uses the assignment a_{i, j} := min(a_{i, j}, a_{i, k} + a_{k, j}).
[1] Ahuja, Magnanti, Orlin: Network Flows, PrenticeHall, 1993 Section 5.6