This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English verison of the page.

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.


Shortest paths from and to all vertices

MuPAD® notebooks are not recommended. Use MATLAB® live scripts instead.

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.


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)


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],

Now the shortest path between all vertices is found according to the edge weights, because no specification was given and defaults are used.


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],
G := Graph::setEdgeWeights(G, Graph::getEdges(G), [2, 1, -3, 2]):






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


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


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

Was this topic helpful?