# Paths and traversal

*Graphs.jl* provides several traversal and shortest-path algorithms, along with various utility functions. Where appropriate, edge distances may be passed in as a matrix of real number values.

Edge distances for most traversals may be passed in as a sparse or dense matrix of values, indexed by `[src,dst]`

vertices. That is, `distmx[2,4] = 2.5`

assigns the distance `2.5`

to the (directed) edge connecting vertex 2 and vertex 4. Note that for undirected graphs `distmx[4,2]`

also has to be set.

Default edge distances may be passed in via the `Graphs.DefaultDistance`

structure.

Any graph traversal will traverse an edge only if it is present in the graph. When a distance matrix is given:

- distance values for undefined edges will be ignored;
- any unassigned values (in sparse distance matrices) for edges that are present in the graph will be assumed to take the default value of 1.0;
- any zero values (in sparse/dense distance matrices) for edges that are present in the graph will instead have an implicit edge cost of 1.0.

## Graph traversal

Graph traversal refers to a process that traverses vertices of a graph following certain order (starting from user-input sources). This package implements three traversal schemes:

`BreadthFirst`

`DepthFirst`

`MaximumAdjacency`

The package also includes uniform random walks and self avoiding walks with the following functions:

`randomwalk`

`non_backtracking_randomwalk`

`self_avoiding_walk`

## Shortest paths

The following properties always hold for shortest path algorithms implemented here:

- The distance from a vertex to itself is always
`0`

. - The distance between two vertices with no connecting edge is always
`Inf`

or`typemax(eltype(distmx))`

.

The `dijkstra_shortest_paths`

, `desopo_pape_shortest_paths`

, `floyd_warshall_shortest_paths`

, `bellman_ford_shortest_paths`

, and `yen_k_shortest_paths`

functions return path states (subtypes of `Graphs.AbstractPathState`

) that contain various information about the graph learned during traversal.

The corresponding state types (with the exception of `YenState`

) have the following common fields:

`state.dists`

holds a vector with the distances computed, indexed by source vertex.`state.parents`

holds a vector of parents of each vertex on the shortest paths (the parent of a source vertex is always`0`

).`YenState`

substitutes`.paths`

for`.parents`

.

In addition, with the appropriate optional arguments, `dijkstra_shortest_paths`

will return information on all possible shortest paths available from the source.