Shortest paths

Graphs.jl includes standard algorithms for shortest paths and longest paths.

Index

Full docs

Graphs.a_starMethod
a_star(g, s, t[, distmx][, heuristic][, edgetype_to_return])

Compute a shortest path using the A* search algorithm.

Return a vector of edges.

Arguments

  • g::AbstractGraph: the graph
  • s::Integer: the source vertex
  • t::Integer: the target vertex
  • distmx::AbstractMatrix: an optional (possibly sparse) n × n matrix of edge weights. It is set to weights(g) by default (which itself falls back on Graphs.DefaultDistance).
  • heuristic: an optional function mapping each vertex to a lower estimate of the remaining distance from v to t. It is set to v -> 0 by default (which corresponds to Dijkstra's algorithm). Note that the heuristic values should have the same type as the edge weights!
  • edgetype_to_return::Type{E}: the type E<:AbstractEdge of the edges in the return vector. It is set to edgetype(g) by default. Note that the two-argument constructor E(u, v) must be defined, even for weighted edges: if it isn't, consider using E = Graphs.SimpleEdge.
Warning

Since a two-argument edge constructor E(u, v) is used to construct the path, metadata associated with the edge (like its weight) will be lost in the result. You might need to code a post-processing step yourself.

source
Graphs.BellmanFordStateType
BellmanFordState{T, U}

An AbstractPathState designed for Bellman-Ford shortest-paths calculations.

Fields

  • parents::Vector{U}: parents[v] is the predecessor of vertex v on the shortest path from the source to v
  • dists::Vector{T}: dists[v] is the length of the shortest path from the source to v
source
Graphs.enumerate_pathsMethod
enumerate_paths(state[, vs])

Given a path state state of type AbstractPathState, return a vector (indexed by vertex) of the paths between the source vertex used to compute the path state and a single destination vertex, a list of destination vertices, 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.

Implementation Notes

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
Graphs.DEsopoPapeStateType
struct DEposoPapeState{T, U}

An AbstractPathState designed for D`Esopo-Pape shortest-path calculations.

Fields

  • parents::Vector{U}: parents[v] is the predecessor of vertex v on the shortest path from the source to v
  • dists::Vector{T}: dists[v] is the length of the shortest path from the source to v
source
Graphs.desopo_pape_shortest_pathsMethod
desopo_pape_shortest_paths(g, src, distmx=weights(g))

Compute shortest paths between a source src and all other nodes in graph g using the D'Esopo-Pape algorithm. Return a Graphs.DEsopoPapeState with relevant traversal information (try querying state.parents or state.dists).

Examples

julia> using Graphs

julia> ds = desopo_pape_shortest_paths(cycle_graph(5), 2);

julia> ds.dists
5-element Vector{Int64}:
 1
 0
 1
 2
 2

julia> ds = desopo_pape_shortest_paths(path_graph(5), 2);

julia> ds.dists
5-element Vector{Int64}:
 1
 0
 1
 2
 3
source
Graphs.DijkstraStateType
struct DijkstraState{T, U}

An AbstractPathState designed for Dijkstra shortest-paths calculations.

Fields

  • parents::Vector{U}
  • dists::Vector{T}
  • predecessors::Vector{Vector{U}}: 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::Vector{Float64}: a vector, indexed by vertex, of the number of shortest paths from the source to that vertex. The path count of a source vertex is always 1.0. The path count of an unreached vertex is always 0.0.
  • closest_vertices::Vector{U}: a vector of all vertices in the graph ordered from closest to farthest.
source
Graphs.dijkstra_shortest_pathsMethod
dijkstra_shortest_paths(g, srcs, distmx=weights(g));

Perform Dijkstra's algorithm on a graph, computing shortest distances between srcs and all other vertices. Return a Graphs.DijkstraState that contains various traversal information (try querying state.parents or state.dists).

Optional Arguments

  • allpaths=false: If true, state.pathcounts holds a vector, indexed by vertex, of the number of shortest paths from the source to that vertex. The path count of a source vertex is always 1.0. The path count of an unreached vertex is always 0.0.
  • trackvertices=false: If true, state.closest_vertices holds a vector of all vertices in the graph ordered from closest to farthest.
  • maxdist (default: typemax(T)) specifies the maximum path distance beyond which all path distances are assumed to be infinite (that is, they do not exist).

Performance

If using a sparse matrix for distmx, you may achieve better performance by passing in a transpose of its sparse transpose. That is, assuming D is the sparse distance matrix:

D = transpose(sparse(transpose(D)))

Be aware that realizing the sparse transpose of D incurs a heavy one-time penalty, so this strategy should only be used when multiple calls to dijkstra_shortest_paths with the distance matrix are planned.

Examples

julia> using Graphs

julia> ds = dijkstra_shortest_paths(cycle_graph(5), 2);

julia> ds.dists
5-element Vector{Int64}:
 1
 0
 1
 2
 2

julia> ds = dijkstra_shortest_paths(path_graph(5), 2);

julia> ds.dists
5-element Vector{Int64}:
 1
 0
 1
 2
 3
source
Graphs.FloydWarshallStateType
struct FloydWarshallState{T, U}

An AbstractPathState designed for Floyd-Warshall shortest-paths calculations.

Fields

  • dists::Matrix{T}: dists[u, v] is the length of the shortest path from u to v
  • parents::Matrix{U}: parents[u, v] is the predecessor of vertex v on the shortest path from u to v
source
Graphs.JohnsonStateType
struct JohnsonState{T, U}

An AbstractPathState designed for Johnson shortest-paths calculations.

Fields

  • dists::Matrix{T}: dists[u, v] is the length of the shortest path from u to v
  • parents::Matrix{U}: parents[u, v] is the predecessor of vertex v on the shortest path from u to v
source
Graphs.johnson_shortest_pathsMethod
johnson_shortest_paths(g, distmx=weights(g))

Use the Johnson algorithm to compute the shortest paths between all pairs of vertices in graph g using an optional distance matrix distmx.

Return a Graphs.JohnsonState with relevant traversal information (try querying state.parents or state.dists).

Performance

Complexity: O(|V|*|E|)

source
Graphs.dag_longest_pathFunction
dag_longest_path(g, distmx=weights(g); topological_order=topological_sort_by_dfs(g))

Return a longest path within the directed acyclic graph g, with distance matrix distmx and using topological_order to iterate on vertices.

source
Graphs.has_negative_edge_cycle_spfaMethod

Function which returns true if there is any negative weight cycle in the graph.

Examples

julia> using Graphs

julia> g = complete_graph(3);

julia> d = [1 -3 1; -3 1 1; 1 1 1];

julia> has_negative_edge_cycle_spfa(g, d)
true

julia> g = complete_graph(4);

julia> d = [1 1 -1 1; 1 1 -1 1; 1 1 1 1; 1 1 1 1];

julia> has_negative_edge_cycle_spfa(g, d)
false
source
Graphs.spfa_shortest_pathsMethod
spfa_shortest_paths(g, s, distmx=weights(g))

Compute shortest paths between a source s and all other nodes in graph g using the Shortest Path Faster Algorithm.

Return a vector of distances to the source.

Examples

julia> using Graphs

julia> g = complete_graph(4);

julia> d = [1 1 -1 1; 1 1 -1 1; 1 1 1 1; 1 1 1 1];

julia> spfa_shortest_paths(g, 1, d)
4-element Vector{Int64}:
  0
  0
 -1
  0
julia> using Graphs

julia> g = complete_graph(3);

julia> d = [1 -3 1; -3 1 1; 1 1 1];

julia> spfa_shortest_paths(g, 1, d)
ERROR: Graphs.NegativeCycleError()
[...]
source
Graphs.YenStateType
struct YenState{T, U}

Designed for yen k-shortest-paths calculations.

Fields

  • dists::Vector{T}: dists[k] is the length of the k-th shortest path from the source to the target
  • paths::Vector{Vector{U}}: paths[k] is the description of the k-th shortest path (as a sequence of vertices) from the source to the target
source
Graphs.yen_k_shortest_pathsMethod
yen_k_shortest_paths(g, source, target, distmx=weights(g), K=1; maxdist=typemax(T));

Perform Yen's algorithm on a graph, computing k-shortest distances between source and target other vertices. Return a YenState that contains distances and paths.

source