Shortest-Path Algorithms
Erdos implements several classical algorithms for finding the shortest paths between one or more vertex and any other vertex in the graphs. For all algorithms the following holds:
- the distance from a vertex to itself is always
0
; - the distance between two vertices with no connecting paths is always
Inf
.
The shortest_paths
method provides easy access to the default algorithm.
Erdos.shortest_paths
— Functionshortest_paths(g, x...; kws...)
Computes shortest paths using Dijkstra's algorithm. See dijkstra_shortest_paths
.
Erdos.a_star
— Functiona_star(g, s, t, distmx=weights(g), heuristic = n->0)
Computes the shortest path between vertices s
and t
using the A* search algorithm. An optional heuristic function and edge distance matrix may be supplied. Returns an empty path if there are no such paths.
Erdos.dijkstra_shortest_paths
— Functiondijkstra_shortest_paths(g, s, distmx=weights(g); allpaths=false)
dijkstra_shortest_paths(g, sources, distmx=weights(g); allpaths=false)
Performs Dijkstra's algorithm on a graph, computing shortest distances between a source vertex s
(or a vector sources
) and all other veritces. Returns a DijkstraState
that contains various traversal information.
With allpaths=true
, returns a DijkstraState
that keeps track of all predecessors of a given vertex.
Erdos.bellman_ford_shortest_paths
— Functionbellman_ford_shortest_paths(g, s, distmx=weights(g))
bellman_ford_shortest_paths(g, sources, distmx=weights(g))
Uses the Bellman-Ford algorithm to compute shortest paths of all vertices of a g
from a source vertex s
(or a set of source vertices sources
). Returns a BellmanFordState
with relevant traversal information.
Erdos.floyd_warshall_shortest_paths
— Functionfloyd_warshall_shortest_paths(g, distmx=weights(g))
Uses the Floyd-Warshall algorithm to compute shortest paths between all pairs of vertices in graph g
. Returns a FloydWarshallState
with relevant traversal information, each is a vertex-indexed vector of vectors containing the metric for each vertex in the graph.
Note that this algorithm may return a large amount of data (it will allocate on the order of $O(nv^2)$).
Path discovery / enumeration
Erdos.enumerate_paths
— Functionenumerate_paths(state::AbstractPathState)
enumerate_paths(state::AbstractPathState, dest)
Given a path state state
of type AbstractPathState
(see below), returns a vector (indexed by vertex) of the paths between the source vertex used to compute the path state and a destination vertex v
, a set of destination vertices vs
, or the entire graph. For multiple destination vertices, each path is represented by a vector of vertices on the path between the source and the destination. Nonexistent paths will be indicated by an empty vector. For single destinations, the path is represented by a single vector of vertices, and will be length 0 if the path does not exist.
For Floyd-Warshall path states, please note that the output is a bit different, since this algorithm calculates all shortest paths for all pairs of vertices: enumerate_paths(state)
will return a vector (indexed by source vertex) of vectors (indexed by destination vertex) of paths. enumerate_paths(state, v)
will return a vector (indexed by destination vertex) of paths from source v
to all other vertices. In addition, enumerate_paths(state, v, d)
will return a vector representing the path from vertex v
to vertex d
.
For Floyd-Warshall path states, please note that the output is a bit different, since this algorithm calculates all shortest paths for all pairs of vertices: enumerate_paths(state)
will return a vector (indexed by source vertex) of vectors (indexed by destination vertex) of paths. enumerate_paths(state, v)
will return a vector (indexed by destination vertex) of paths from source v
to all other vertices. In addition, enumerate_paths(state, v, d)
will return a vector representing the path from vertex v
to vertex d
.
Path States
The floyd_warshall_shortest_paths
, bellman_ford_shortest_paths
, dijkstra_shortest_paths
, and dijkstra_predecessor_and_distance
functions return a state that contains various information about the graph learned during traversal. The three state types have the following common information, accessible via the type:
.dists
Holds a vector of distances computed, indexed by source vertex.
.parents
Holds a vector of parents of each source vertex. The parent of a source vertex is always 0
.
In addition, the dijkstra_predecessor_and_distance
function stores the following information:
.predecessors
Holds a vector, indexed by vertex, of all the predecessors discovered during shortest-path calculations. This keeps track of all parents when there are multiple shortest paths available from the source.
.pathcounts
Holds a vector, indexed by vertex, of the path counts discovered during traversal. This equals the length of each subvector in the .predecessors
output above.