dijkstra

Dijkstra’s algorithm for single-source shortest paths in graphs with non-negative edge weights.

Dijkstra’s algorithm finds the shortest path from a source node to all other reachable nodes in a graph. It works by maintaining a priority queue of nodes to visit, always expanding the node with the smallest known distance.

Algorithm

Algorithm	Function	Complexity	Best For
Dijkstra (single-target)	`shortest_path/6`	O((V + E) log V)	One-to-one shortest path
Dijkstra (single-source)	`single_source_distances/5`	O((V + E) log V)	One-to-all shortest paths
Implicit Dijkstra	`implicit_dijkstra/6`	O((V + E) log V)	Large/infinite graphs

Key Concepts

Greedy Strategy: Always expands the node with minimum tentative distance
Priority Queue: Min-heap ordered by current best distance
Relaxation: Update distances when a shorter path is found
Non-Negative Weights: Required for correctness (use Bellman-Ford for negative weights)

Comparison with Other Algorithms

Algorithm	Handles Negative Weights	Complexity	Use Case
Dijkstra	❌ No	O((V+E) log V)	General shortest paths
A*	❌ No	O((V+E) log V)	When good heuristic available
Bellman-Ford	✅ Yes	O(VE)	Negative weights, cycle detection
Floyd-Warshall	✅ Yes	O(V³)	All-pairs shortest paths

History

Edsger W. Dijkstra published this algorithm in 1959. The original paper described it for finding the shortest path between two nodes, but it’s commonly used for single-source shortest paths to all nodes.

Use Cases

Network routing: OSPF, IS-IS protocols use Dijkstra
Map services: Shortest driving directions
Social networks: Degrees of separation
Game development: Shortest path on weighted grids

References

Values

do_dijkstra

</>

pub fn do_dijkstra(
  graph: model.Graph(n, e),
  goal: Int,
  frontier: pairing_heap.Heap(#(e, List(Int))),
  visited: dict.Dict(Int, e),
  add: fn(e, e) -> e,
  compare: fn(e, e) -> order.Order,
) -> option.Option(#(e, List(Int)))

implicit_dijkstra

</>

pub fn implicit_dijkstra(
  from start: state,
  successors_with_cost successors: fn(state) -> List(
    #(state, cost),
  ),
  is_goal is_goal: fn(state) -> Bool,
  with_zero zero: cost,
  with_add add: fn(cost, cost) -> cost,
  with_compare compare: fn(cost, cost) -> order.Order,
) -> option.Option(cost)

Finds the shortest path in an implicit graph using Dijkstra’s algorithm.

Instead of a materialized Graph, this uses a successors_with_cost function to compute weighted neighbors on demand.

Returns the shortest distance to any state satisfying is_goal, or None if no goal state is reachable.

Time Complexity: O((V + E) log V) where V is visited states and E is explored transitions

Parameters

successors_with_cost: Function that generates weighted successors for a state
is_goal: Predicate that identifies goal states
zero: The identity element for addition (e.g., 0 for integers)
add: Function to add two costs
compare: Function to compare two costs

implicit_dijkstra_by

</>

pub fn implicit_dijkstra_by(
  from start: state,
  successors_with_cost successors: fn(state) -> List(
    #(state, cost),
  ),
  visited_by key_fn: fn(state) -> key,
  is_goal is_goal: fn(state) -> Bool,
  with_zero zero: cost,
  with_add add: fn(cost, cost) -> cost,
  with_compare compare: fn(cost, cost) -> order.Order,
) -> option.Option(cost)

Like implicit_dijkstra, but deduplicates visited states by a custom key.

Essential when your state carries extra data beyond what defines identity. The visited_by function extracts the deduplication key from each state.

Time Complexity: O((V + E) log V) where V and E are measured in unique keys

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(utils.Path(e))

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

Works with non-negative edge weights only.

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

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

shortest_path_float

</>

pub fn shortest_path_float(
  in graph: model.Graph(n, Float),
  from start: Int,
  to goal: Int,
) -> option.Option(utils.Path(Float))

Finds the shortest path using float weights.

This is a convenience wrapper around shortest_path that uses:

0.0 as the zero element
float.add for addition
float.compare for comparison

Example

dijkstra.shortest_path_float(graph, from: 1, to: 5)
// => Some(Path([1, 2, 5], 15.5))

When to Use

Use this for graphs with Float edge weights (probabilities, distances in kilometers with decimal precision, continuous costs, etc.). Note that float arithmetic has precision limitations - for exact calculations, prefer Int weights (e.g., store cents instead of dollars).

shortest_path_int

</>

pub fn shortest_path_int(
  in graph: model.Graph(n, Int),
  from start: Int,
  to goal: Int,
) -> option.Option(utils.Path(Int))

Finds the shortest path using integer weights.

This is a convenience wrapper around shortest_path that uses:

0 as the zero element
int.add for addition
int.compare for comparison

Example

// Much cleaner than the full explicit version
dijkstra.shortest_path_int(graph, from: 1, to: 5)
// => Some(Path([1, 2, 5], 15))

// Equivalent explicit call:
// dijkstra.shortest_path(
//   graph, from: 1, to: 5,
//   with_zero: 0,
//   with_add: int.add,
//   with_compare: int.compare
// )

When to Use

Use this for graphs with Int edge weights (hop counts, distances in meters, costs in cents, etc.). For custom weight types (Money, Distance, etc.), use the full shortest_path function with your own semiring operations.

single_source_distances

</>

pub fn single_source_distances(
  in graph: model.Graph(n, e),
  from source: Int,
  with_zero zero: e,
  with_add add: fn(e, e) -> e,
  with_compare compare: fn(e, e) -> order.Order,
) -> dict.Dict(Int, e)

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.

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

single_source_distances_float

</>

pub fn single_source_distances_float(
  in graph: model.Graph(n, Float),
  from source: Int,
) -> dict.Dict(Int, Float)

Computes shortest distances using float weights.

Convenience wrapper for single_source_distances with Float weights.

single_source_distances_int

</>

pub fn single_source_distances_int(
  in graph: model.Graph(n, Int),
  from source: Int,
) -> dict.Dict(Int, Int)

Computes shortest distances using integer weights.

Convenience wrapper for single_source_distances with Int weights.