Documentation Center

  • Trial Software
  • Product Updates

Contents

Graph::shortestPathAllPairs

Shortest paths from and to all vertices

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

Graph::shortestPathAllPairs(G, <SearchFor = Weights | Costs>)

Description

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)

Examples

Example 1

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)

Example 2

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)

Parameters

G

Graph

Options

SearchFor

Defines whether the weights of the graph are considered or the costs. Default is Weights.

Return Values

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).

Algorithms

The algorithm is also known as Floyd-Warshall or Roy-Warshall algorithm. The idea behind it is to solve the problem by continuous matrix multiplication. he only difference is that Floyd uses the assignment ai, j := min(ai, j, ai, k + ak, j).

References

[1] Ahuja, Magnanti, Orlin: Network Flows, Prentice-Hall, 1993 Section 5.6

Was this topic helpful?