|
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.
ShortestPath(u, v : parameters) : GrphVert, GrphVert -> Eseq
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.
ShortestPaths(u : parameters) : GrphVert -> Eseq
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.
HasNegativeWeightCycle(G) : GrphMult -> BoolElt
Return true if and only if the graph G has negative-weight cycles.
AllPairsShortestPaths(G : parameters) : GrphMult -> SeqEnum, SeqEnum
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.
We create a weighted multidigraph.
> 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 > 2
We 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}.
We create a weighted multigraph with one edge assigned a negative
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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|