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 — Function.

shortest_paths(g, x...; kws...)

Computes shortest paths using Dijkstra's algorithm. See dijkstra_shortest_paths.

source

# Erdos.a_star — Function.

a_star(g, s, t, distmx=ConstEdgeMap(g,1), 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.

source

# Erdos.dijkstra_shortest_paths — Function.

dijkstra_shortest_paths(g, s, distmx=ConstEdgeMap(g,1); allpaths=false)
dijkstra_shortest_paths(g, sources, distmx=ConstEdgeMap(g,1); 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.

source

# Erdos.bellman_ford_shortest_paths — Function.

bellman_ford_shortest_paths(g, s, distmx=ConstEdgeMap(g,1))
bellman_ford_shortest_paths(g, sources, distmx=ConstEdgeMap(g,1))

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.

source

# Erdos.floyd_warshall_shortest_paths — Function.

floyd_warshall_shortest_paths(g, distmx=ConstEdgeMap(g,1))

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

source

Path discovery / enumeration

# Erdos.enumerate_paths — Function.

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

source

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.