# Shortest paths

*Graphs.jl* includes standard algorithms for shortest paths.

## Index

`Graphs.BellmanFordState`

`Graphs.DEsopoPapeState`

`Graphs.DijkstraState`

`Graphs.FloydWarshallState`

`Graphs.JohnsonState`

`Graphs.YenState`

`Graphs.a_star`

`Graphs.bellman_ford_shortest_paths`

`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`

— Method`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`

.

`Graphs.BellmanFordState`

— Type`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`

`Graphs.bellman_ford_shortest_paths`

— Method```
bellman_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`

— Method`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`

.

`Graphs.DEsopoPapeState`

— Type`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`

`Graphs.desopo_pape_shortest_paths`

— Method`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
```

`Graphs.DijkstraState`

— Type`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.

`Graphs.dijkstra_shortest_paths`

— Method`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
```

`Graphs.FloydWarshallState`

— Type`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`

`Graphs.floyd_warshall_shortest_paths`

— Method`floyd_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`

— Type`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`

`Graphs.johnson_shortest_paths`

— Method`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|)`

`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`

— Method`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()
[...]
```

`Graphs.YenState`

— Type`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

`Graphs.yen_k_shortest_paths`

— Method`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.