libgraph v0.13.3 Graph.Pathfinding

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

Link to this section Summary

Functions

a_star(g, a, b, hfun)

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

all(g, a, b)

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

dijkstra(g, a, b)

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()

heuristic_fun() :: (Graph.vertex() -> integer())

Link to this section Functions

a_star(g, a, b, hfun)

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)

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.

dijkstra(g, a, b)

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.