Graph.Pathfinding
(multigraph v0.16.1-mg.2)
Copy Markdown
This module contains implementation code for path finding algorithms used by libgraph.
Summary
Functions
Finds the shortest path between a and b as a list of vertices.
Returns nil if no path can be found.
Finds all paths between a and b, each path as a list of vertices.
Returns nil if no path can be found.
Finds the shortest path between a and b as a list of vertices.
Returns nil if no path can be found.
Types
@type heuristic_fun() :: (Graph.vertex() -> integer())
Functions
@spec a_star(Graph.t(), Graph.vertex(), Graph.vertex(), heuristic_fun()) :: [Graph.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.
@spec all(Graph.t(), Graph.vertex(), Graph.vertex()) :: [[Graph.vertex()]] | nil
Finds all paths between a and b, each path as a list of vertices.
Returns nil if no path can be found.
@spec bellman_ford(Graph.t(), Graph.vertex()) :: %{required(Graph.vertex()) => integer() | :infinity} | nil
@spec dijkstra(Graph.t(), Graph.vertex(), Graph.vertex()) :: [Graph.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.