yog/pathfinding

Types

BellmanFordResult

Result type for Bellman-Ford algorithm.

pub type BellmanFordResult(e) {
  ShortestPath(path: Path(e))
  NegativeCycle
  NoPath
}

Constructors

```
ShortestPath(path: Path(e))
```
A shortest path was found successfully
```
NegativeCycle
```
A negative cycle was detected (reachable from source)
```
NoPath
```
No path exists from start to goal

Path

</>

Represents a path through the graph with its total weight.

pub type Path(e) {
  Path(nodes: List(Int), total_weight: e)
}

Constructors

```
Path(nodes: List(Int), total_weight: e)
```

Values

a_star

</>

pub fn a_star(
  in graph: model.Graph(n, e),
  from start: Int,
  to goal: Int,
  with_zero zero: e,
  with_add add: fn(e, e) -> e,
  with_compare compare: fn(e, e) -> order.Order,
  heuristic h: fn(Int, Int) -> e,
) -> option.Option(Path(e))

Finds the shortest path using A* search with a heuristic function.

A* is more efficient than Dijkstra when you have a good heuristic estimate of the remaining distance to the goal. The heuristic must be admissible (never overestimate the actual distance) to guarantee finding the shortest path.

Time Complexity: O((V + E) log V), but often faster than Dijkstra in practice

Parameters

heuristic: A function that estimates distance from any node to the goal. Must be admissible (h(n) ≤ actual distance) to guarantee shortest path.

Example

// Manhattan distance heuristic for grid
let h = fn(node, goal) {
  int.absolute_value(node.x - goal.x) + int.absolute_value(node.y - goal.y)
}

pathfinding.a_star(
  in: graph,
  from: start,
  to: goal,
  with_zero: 0,
  with_add: int.add,
  with_compare: int.compare,
  heuristic: h
)

bellman_ford

</>

pub fn bellman_ford(
  in graph: model.Graph(n, e),
  from start: Int,
  to goal: Int,
  with_zero zero: e,
  with_add add: fn(e, e) -> e,
  with_compare compare: fn(e, e) -> order.Order,
) -> BellmanFordResult(e)

Finds shortest path with support for negative edge weights using Bellman-Ford.

Unlike Dijkstra and A*, this algorithm can handle negative edge weights. It also detects negative cycles reachable from the source node.

Time Complexity: O(VE) where V is vertices and E is edges

Returns

ShortestPath(path): If a valid shortest path exists
NegativeCycle: If a negative cycle is reachable from the start node
NoPath: If no path exists from start to goal

Example

pathfinding.bellman_ford(
  in: graph,
  from: 1,
  to: 5,
  with_zero: 0,
  with_add: int.add,
  with_compare: int.compare
)
// => ShortestPath(Path([1, 3, 5], -2))  // Can have negative total weight
// or NegativeCycle                       // If cycle detected
// or NoPath                              // If unreachable

shortest_path

</>

pub fn shortest_path(
  in graph: model.Graph(n, e),
  from start: Int,
  to goal: Int,
  with_zero zero: e,
  with_add add: fn(e, e) -> e,
  with_compare compare: fn(e, e) -> order.Order,
) -> option.Option(Path(e))

Finds the shortest path between two nodes using Dijkstra’s algorithm.

Works with non-negative edge weights only. For negative weights, use bellman_ford.

Time Complexity: O((V + E) log V) with heap

Parameters

zero: The identity element for addition (e.g., 0 for integers)
add: Function to add two weights
compare: Function to compare two weights

Example

pathfinding.shortest_path(
  in: graph,
  from: 1,
  to: 5,
  with_zero: 0,
  with_add: int.add,
  with_compare: int.compare
)
// => Some(Path([1, 2, 5], 15))