Graph.Pathfinding (libgraph v0.16.0)
This module contains implementation code for path finding algorithms used by libgraph.
Link to this section 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.
Link to this section Types
heuristic_fun()
@type heuristic_fun() :: (Graph.vertex() -> integer())
Link to this section Functions
a_star(g, a, b, hfun)
@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.
all(g, a, b)
@spec all(Graph.t(), Graph.vertex(), Graph.vertex()) :: [Graph.vertex()]
Finds all paths between a and b, each path as a list of vertices.
Returns nil if no path can be found.
bellman_ford(g, a)
@spec bellman_ford(Graph.t(), Graph.vertex()) :: [Graph.vertex()]
dijkstra(g, a, b)
@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.