# `Multigraph.Pathfinding`

This module contains implementation code for path finding algorithms used by `libgraph`.

# `heuristic_fun`

```elixir
@type heuristic_fun() :: (Multigraph.vertex() -> integer())
```

# `a_star`

```elixir
@spec a_star(
  Multigraph.t(),
  Multigraph.vertex(),
  Multigraph.vertex(),
  heuristic_fun()
) ::
  [Multigraph.vertex()] | nil
```

Finds the shortest path between `a` and `b` as a list of vertices.
Returns `nil` if no path can be found.

This implementation takes a heuristic function which allows you to
calculate the lower bound cost of a given vertex `v`. The algorithm
then uses that lower bound function to determine which path to explore
next in the graph.

The `dijkstra` function is simply `a_star` where the heuristic function
always returns 0, and thus the next vertex is chosen based on the weight of
the edge between it and the current vertex.

# `a_star`

# `all`

```elixir
@spec all(Multigraph.t(), Multigraph.vertex(), Multigraph.vertex()) ::
  [[Multigraph.vertex()]] | nil
```

Finds all paths between `a` and `b`, each path as a list of vertices.
Returns `nil` if no path can be found.

# `bellman_ford`

```elixir
@spec bellman_ford(Multigraph.t(), Multigraph.vertex()) ::
  %{required(Multigraph.vertex()) => integer() | :infinity} | nil
```

# `bellman_ford`

# `dijkstra`

```elixir
@spec dijkstra(Multigraph.t(), Multigraph.vertex(), Multigraph.vertex()) ::
  [Multigraph.vertex()] | nil
```

Finds the shortest path between `a` and `b` as a list of vertices.
Returns `nil` if no path can be found.

The shortest path is calculated here by using a cost function to choose
which path to explore next. The cost function in Dijkstra's algorithm is
`weight(E(A, B))+lower_bound(E(A, B))` where `lower_bound(E(A, B))` is always 0.

# `dijkstra`

---

*Consult [api-reference.md](api-reference.md) for complete listing*