Shortest paths
Graphs.jl includes standard algorithms for shortest paths and longest paths.
Index
Graphs.BellmanFordState
Graphs.DEsopoPapeState
Graphs.DijkstraState
Graphs.FloydWarshallState
Graphs.JohnsonState
Graphs.YenState
Graphs.a_star
Graphs.bellman_ford_shortest_paths
Graphs.dag_longest_path
Graphs.desopo_pape_shortest_paths
Graphs.dijkstra_shortest_paths
Graphs.enumerate_paths
Graphs.floyd_warshall_shortest_paths
Graphs.has_negative_edge_cycle_spfa
Graphs.johnson_shortest_paths
Graphs.spfa_shortest_paths
Graphs.yen_k_shortest_paths
Full docs
Graphs.a_star
— Methoda_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 graphs::Integer
: the source vertext::Integer
: the target vertexdistmx::AbstractMatrix
: an optional (possibly sparse)n × n
matrix of edge weights. It is set toweights(g)
by default (which itself falls back onGraphs.DefaultDistance
).heuristic
: an optional function mapping each vertex to a lower estimate of the remaining distance fromv
tot
. It is set tov -> 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 typeE<:AbstractEdge
of the edges in the return vector. It is set toedgetype(g)
by default. Note that the two-argument constructorE(u, v)
must be defined, even for weighted edges: if it isn't, consider usingE = Graphs.SimpleEdge
.
Graphs.BellmanFordState
— TypeBellmanFordState{T, U}
An AbstractPathState
designed for Bellman-Ford shortest-paths calculations.
Fields
parents::Vector{U}
:parents[v]
is the predecessor of vertexv
on the shortest path from the source tov
dists::Vector{T}
:dists[v]
is the length of the shortest path from the source tov
Graphs.bellman_ford_shortest_paths
— Methodbellman_ford_shortest_paths(g, s, distmx=weights(g))
bellman_ford_shortest_paths(g, ss, distmx=weights(g))
Compute shortest paths between a source s
(or list of sources ss
) and all other nodes in graph g
using the Bellman-Ford algorithm.
Return a Graphs.BellmanFordState
with relevant traversal information (try querying state.parents
or state.dists
).
Graphs.enumerate_paths
— Methodenumerate_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
.
Graphs.DEsopoPapeState
— Typestruct DEposoPapeState{T, U}
An AbstractPathState
designed for D`Esopo-Pape shortest-path calculations.
Fields
parents::Vector{U}
:parents[v]
is the predecessor of vertexv
on the shortest path from the source tov
dists::Vector{T}
:dists[v]
is the length of the shortest path from the source tov
Graphs.desopo_pape_shortest_paths
— Methoddesopo_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
Graphs.DijkstraState
— Typestruct 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 always1.0
. The path count of an unreached vertex is always0.0
.closest_vertices::Vector{U}
: a vector of all vertices in the graph ordered from closest to farthest.
Graphs.dijkstra_shortest_paths
— Methoddijkstra_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 always1.0
. The path count of an unreached vertex is always0.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
Graphs.FloydWarshallState
— Typestruct 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 fromu
tov
parents::Matrix{U}
:parents[u, v]
is the predecessor of vertexv
on the shortest path fromu
tov
Graphs.floyd_warshall_shortest_paths
— Methodfloyd_warshall_shortest_paths(g, distmx=weights(g))
Use the Floyd-Warshall algorithm to compute the shortest paths between all pairs of vertices in graph g
using an optional distance matrix distmx
. Return a Graphs.FloydWarshallState
with relevant traversal information (try querying state.parents
or state.dists
).
Performance
Space complexity is on the order of O(|V|^2)
.
Graphs.JohnsonState
— Typestruct 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 fromu
tov
parents::Matrix{U}
:parents[u, v]
is the predecessor of vertexv
on the shortest path fromu
tov
Graphs.johnson_shortest_paths
— Methodjohnson_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|)
Graphs.dag_longest_path
— Functiondag_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.
Graphs.has_negative_edge_cycle_spfa
— MethodFunction 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
Graphs.spfa_shortest_paths
— Methodspfa_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()
[...]
Graphs.YenState
— Typestruct YenState{T, U}
Designed for yen k-shortest-paths calculations.
Fields
dists::Vector{T}
:dists[k]
is the length of thek
-th shortest path from the source to the targetpaths::Vector{Vector{U}}
:paths[k]
is the description of thek
-th shortest path (as a sequence of vertices) from the source to the target
Graphs.yen_k_shortest_paths
— Methodyen_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.