Two standard algorithms have been implemented for finding single-source shortest paths in weighted graphs. One is Dijsktra's algorithm for graphs without negative weight cycles, the second is Bellman-Ford's for those graphs with negative weight cycles. Dijsktra's algorithm is implemented either by a priority queue (binary heap) or a Fibonacci heap. The Fibonacci heap is asymptotically faster for sparse graphs. But for most practical purposes (graphs of small order) the binary heap outperforms the Fibonacci heap and is therefore chosen as the default data structure wherever relevant.
Johnson's algorithm has been chosen for the all-pairs shortest paths computation. Indeed, it outperforms the simpler Floyd's algorithm, especially as the graphs get larger.
Finally, Prim's algorithm is used to implement the minimum weight tree computation for undirected graphs. (The tree is a spanning tree if and only if the graph is connected.)
All the functions described below apply to general graphs whose edges are assigned a weight. If the graph under consideration is not weighted, then all its edges are assumed to have weight one. To assign weights to the edges of a graph, see Subsection Edge Decorations. Note that all the functions described below accept negatively weighted edges.
UseFibonacciHeap: Bool Default: false
Return true if and only there is a path from vertex u to vertex v. If true, also returns the distance between u and v.
UseFibonacciHeap: Bool Default: false
Given vertices u and v in a graph G, computes the distance from u to v. Results in an error if there is no path in G from u to v.
UseFibonacciHeap: Bool Default: false
Given a vertex u in a graph G, computes the sequence D of distances from u to v, v any vertex in G. Given any vertex v in G, let i be Index(v). Then D[i], if defined, is the distance from u to v. If there is no path from u to v, then the sequence element D[i] is undefined.
UseFibonacciHeap: Bool Default: false
Return true if and only there is a path from vertex u to vertex v in the parent graph G. If so, also returns a shortest path from u to v as a sequence of edges of G.
UseFibonacciHeap: Bool Default: false
Given vertices u and v in a graph G, computes a shortest path from u to v as a sequence of edges of G. Results in an error if there is no path in G from u to v.
UseFibonacciHeap: Bool Default: false
Given a vertex u in a graph G, computes the sequence P of shortest paths from u to v, for every vertex v in G. Given any vertex v in G, let i be Index(v). If there exists a path from u to v then P[i] is a sequence of edges giving a shortest path from u to v. If there is no path from u to v, then the sequence element P[i] is undefined.
UseFibonacciHeap: Bool Default: false
Return true if and only there is a path from vertex u to vertex v in the parent graph G. If true, also returns a shortest path from u to v as a sequence of vertices of G.
UseFibonacciHeap: Bool Default: false
Given vertices u and v in a graph G, this function computes a shortest path from u to v as a sequence of vertices of G. An error results if there is no path in G from u to v.
UseFibonacciHeap: Bool Default: false
Given a vertex u in a graph G, this function computes the sequence P of shortest paths from u to v, for every vertex v in G. Given any vertex v in G, let i be Index(v). If there exists a path from u to v then P[i] is a sequence of vertices specifying a shortest path from u to v. If there is no path from u to v, then the sequence element P[i] is undefined.
Return true if and only if there is a negative-weight cycle reachable from vertex u.
Return true if and only if the graph G has negative-weight cycles.
UseFibonacciHeap: Bool Default: false
Computes the all-pairs shortest paths. Let u and v be two vertices of a graph G and let i = (Index(u)) and j = (Index(v)). Let S1 and S2 be the two sequences returned by AllPairsShortestPaths, and let s1 = S1[i] and s2 = S2[i]. Then s1[j], if defined, gives the distance from u to v and s2[j], if defined, gives the vertex preceding v in the shortest path from u to v. An error results if the graph G has a negative-weight cycle.
UseFibonacciHeap: Bool Default: false
Returns a minimum weight tree rooted at vertex u, u any vertex of an undirected graph G, as a subgraph of G. The tree spans G if and only if G is connected. The support of G as well as the vertex and edge decorations in G are transferred to the tree.
> G := MultiDigraph< 5 | [1, 2], [1, 2], [1, 3], [2, 4], [3, 5], [3, 4], [4, 5] >; > E := EdgeSet(G); > AssignWeight(~G, E.1, 1); > AssignWeight(~G, E.2, 5); > AssignWeight(~G, E.3, 10); > AssignWeight(~G, E.4, 1); > AssignWeight(~G, E.5, -5); > AssignWeight(~G, E.6, 1); > AssignWeight(~G, E.7, 2); > > > V := VertexSet(G); > E := EdgeSet(G); > for e in E do > e, " ", Weight(e); > end for; < [1, 3], 3 > 10 < [1, 2], 2 > 5 < [1, 2], 1 > 1 < [2, 4], 4 > 1 < [3, 4], 6 > 1 < [3, 5], 5 > -5 < [4, 5], 7 > 2We verify that it has no negative weight cycle reachable from vertex 1, and that there is a path from vertex 1 to vertex 5.
> HasNegativeWeightCycle(V!1); false > b, d := Reachable(V!1, V!5); > assert b; > P := Path(V!1, V!5); > G := Geodesic(V!1, V!5); > > d; 4 > P; [ < [1, 2], 1 >, < [2, 4], 4 >, < [4, 5], 7 > ] > G; [ 1, 2, 4, 5 ]Finally, we verify that the shortest path found has length 4.
> dP := 0; > for e in P do > dP +:= Weight(e); > end for; > assert dP eq d;Note that had we taken instead an undirected graph, we would have had to assign only positive weights to the edges of the graph: any undirected edge {u, v} with negative weight results in the negative weight cycles {u, u} and {v, v}.
weight.
> G := MultiGraph< 5 | {1, 2}, {1, 2}, {1, 3}, {2, 4}, {3, 5}, {3, 4}, {4, 5} >;
> E := EdgeSet(G);
> AssignWeight(~G, E.1, 1);
> AssignWeight(~G, E.3, 5);
> AssignWeight(~G, E.5, 10);
> AssignWeight(~G, E.7, 1);
> AssignWeight(~G, E.9, -5);
> AssignWeight(~G, E.11, 1);
> AssignWeight(~G, E.13, 2);
>
> V := VertexSet(G);
> E := EdgeSet(G);
> for e in E do
> e, " ", Weight(e);
> end for;
< {1, 3}, 5 > 10
< {1, 2}, 3 > 5
< {1, 2}, 1 > 1
< {2, 4}, 7 > 1
< {3, 4}, 11 > 1
< {3, 5}, 9 > -5
< {4, 5}, 13 > 2
We compute a minimum weight spanning tree rooted at vertex 1.
> T := MinimumWeightTree(V!1);
> ET := EdgeSet(T);
> for e in ET do
> e, " ", Weight(e);
> end for;
< {1, 2}, 1 > 1
< {2, 4}, 5 > 1
< {3, 5}, 7 > -5
< {3, 4}, 3 > 1
We compute any other spanning tree rooted at vertex 1
(say a depth first tree
using DFSTree),
and verify that the weights of the edges in G corresponding
to the edges of the tree sum up to a total weight which is no
smaller than the weight of the minimum weight spanning tree.
> DFST := DFSTree(V!1);
> EDT := EdgeSet(DFST);
> for e in EDT do
> u := InitialVertex(e);
> v := TerminalVertex(e);
> w := Min([ Weight(edge) : edge in Edges(V!u, V!v) ]);
> e, " ", w;
> end for;
< {1, 3}, 1 > 10
< {2, 4}, 7 > 1
< {3, 4}, 3 > 1
< {4, 5}, 5 > 2