Documentation |
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)
SearchFor |
Defines whether the weights of the graph are considered or the costs. Default is Weights. |
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).