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
)

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

Computes shortest paths between all pairs of nodes using the Floyd-Warshall algorithm.

Returns a nested dictionary where distances[i][j] gives the shortest distance from node i to node j. If no path exists between two nodes, the pair will not be present in the dictionary.

Returns Error(Nil) if a negative cycle is detected in the graph.

Time Complexity: O(V³) Space Complexity: O(V²)

Parameters

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

Example

import gleam/dict
import gleam/int
import gleam/io
import yog
import yog/pathfinding

pub fn main() {
  let graph =
    yog.directed()
    |> yog.add_node(1, "A")
    |> yog.add_node(2, "B")
    |> yog.add_node(3, "C")
    |> yog.add_edge(from: 1, to: 2, with: 4)
    |> yog.add_edge(from: 2, to: 3, with: 3)
    |> yog.add_edge(from: 1, to: 3, with: 10)

  case pathfinding.floyd_warshall(
    in: graph,
    with_zero: 0,
    with_add: int.add,
    with_compare: int.compare
  ) {
    Ok(distances) -> {
      // Query distance from node 1 to node 3
      let assert Ok(row) = dict.get(distances, 1)
      let assert Ok(dist) = dict.get(row, 3)
      // dist = 7 (via node 2: 4 + 3)
      io.println("Distance from 1 to 3: " <> int.to_string(dist))
    }
    Error(Nil) -> io.println("Negative cycle detected!")
  }
}

Handling Negative Weights

Floyd-Warshall can handle negative edge weights and will detect negative cycles:

let graph_with_negative_cycle =
  yog.directed()
  |> yog.add_node(1, "A")
  |> yog.add_node(2, "B")
  |> yog.add_edge(from: 1, to: 2, with: 5)
  |> yog.add_edge(from: 2, to: 1, with: -10)

case pathfinding.floyd_warshall(
  in: graph_with_negative_cycle,
  with_zero: 0,
  with_add: int.add,
  with_compare: int.compare
) {
  Ok(_) -> io.println("No negative cycle")
  Error(Nil) -> io.println("Negative cycle detected!")  // This will execute
}

Use Cases

• Computing distance matrices for all node pairs
• Finding transitive closure of a graph
• Detecting negative cycles
• Preprocessing for queries about arbitrary node pairs
• Graph metrics (diameter, centrality)

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

Computes shortest distances from a source node to all reachable nodes.

Returns a dictionary mapping each reachable node to its shortest distance from the source. Unreachable nodes are not included in the result.

This is useful when you need distances to multiple destinations, or want to find the closest target among many options. More efficient than running shortest_path multiple times.

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

// Find distances from node 1 to all reachable nodes
let distances = pathfinding.single_source_distances(
  in: graph,
  from: 1,
  with_zero: 0,
  with_add: int.add,
  with_compare: int.compare
)
// => dict.from_list([#(1, 0), #(2, 5), #(3, 8), #(4, 15)])

// Find closest target among many options
let targets = [10, 20, 30]
let closest = targets
  |> list.filter_map(fn(t) { dict.get(distances, t) })
  |> list.sort(int.compare)
  |> list.first

Use Cases

• Finding nearest target among multiple options
• Computing distance maps for game AI
• Network routing table generation
• Graph analysis (centrality measures)
• Reverse pathfinding (with transform.transpose)