Dijkstra (yog-fsharp)

Dijkstra Module

Namespace: Yog.Pathfinding
Assembly: Yog.FSharp.dll

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)	shortestPath	O((V + E) log V)	One-to-one shortest path
Dijkstra (single-source)	singleSourceDistances	O((V + E) log V)	One-to-all shortest paths
Implicit Dijkstra	implicitDijkstra	O((V + E) log V)	Large/infinite graphs

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

Functions and values

Function or value	Description
`implicitDijkstra zero add compare successors isGoal start` Full Usage: `implicitDijkstra zero add compare successors isGoal start` Parameters: zero : `'cost` add : `'cost -> 'cost -> 'cost` compare : `'cost -> 'cost -> int` successors : `'state -> ('state * 'cost) list` isGoal : `'state -> bool` start : `'state` Returns: `'cost option`	Finds the shortest path in an implicit graph using Dijkstra's algorithm. zero : `'cost` add : `'cost -> 'cost -> 'cost` compare : `'cost -> 'cost -> int` successors : `'state -> ('state * 'cost) list` isGoal : `'state -> bool` start : `'state` Returns: `'cost option`
`implicitDijkstraBy zero add compare successors keyFn isGoal start` Full Usage: `implicitDijkstraBy zero add compare successors keyFn isGoal start` Parameters: zero : `'cost` add : `'cost -> 'cost -> 'cost` compare : `'cost -> 'cost -> int` successors : `'state -> ('state * 'cost) list` keyFn : `'state -> 'key` isGoal : `'state -> bool` start : `'state` Returns: `'cost option`	Like `implicitDijkstra`, but deduplicates visited states by a custom key. zero : `'cost` add : `'cost -> 'cost -> 'cost` compare : `'cost -> 'cost -> int` successors : `'state -> ('state * 'cost) list` keyFn : `'state -> 'key` isGoal : `'state -> bool` start : `'state` Returns: `'cost option`
`shortestPath zero add compare start goal graph` Full Usage: `shortestPath zero add compare start goal graph` Parameters: zero : `'e` add : `'e -> 'e -> 'e` compare : `'e -> 'e -> int` start : `NodeId` goal : `NodeId` graph : `Graph<'n, 'e>` Returns: `Path<'e> option`	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) zero : `'e` add : `'e -> 'e -> 'e` compare : `'e -> 'e -> int` start : `NodeId` goal : `NodeId` graph : `Graph<'n, 'e>` Returns: `Path<'e> option`
`shortestPathFloat start goal graph` Full Usage: `shortestPathFloat start goal graph` Parameters: start : `NodeId` goal : `NodeId` graph : `Graph<'n, float>` Returns: `Path<float> option`	Finds the shortest path using float weights. start : `NodeId` goal : `NodeId` graph : `Graph<'n, float>` Returns: `Path<float> option`
`shortestPathInt start goal graph` Full Usage: `shortestPathInt start goal graph` Parameters: start : `NodeId` goal : `NodeId` graph : `Graph<'n, int>` Returns: `Path<int> option`	Finds the shortest path using integer weights. start : `NodeId` goal : `NodeId` graph : `Graph<'n, int>` Returns: `Path<int> option`
`singleSourceDistances zero add compare source graph` Full Usage: `singleSourceDistances zero add compare source graph` Parameters: zero : `'e` add : `'e -> 'e -> 'e` compare : `'e -> 'e -> int` source : `NodeId` graph : `Graph<'n, 'e>` Returns: `Map<NodeId, 'e>`	Computes shortest distances from a source node to all reachable nodes. Returns a Map of each reachable node to its shortest distance. zero : `'e` add : `'e -> 'e -> 'e` compare : `'e -> 'e -> int` source : `NodeId` graph : `Graph<'n, 'e>` Returns: `Map<NodeId, 'e>`
`singleSourceDistancesFloat source graph` Full Usage: `singleSourceDistancesFloat source graph` Parameters: source : `NodeId` graph : `Graph<'n, float>` Returns: `Map<NodeId, float>`	Computes shortest distances using float weights. source : `NodeId` graph : `Graph<'n, float>` Returns: `Map<NodeId, float>`
`singleSourceDistancesInt source graph` Full Usage: `singleSourceDistancesInt source graph` Parameters: source : `NodeId` graph : `Graph<'n, int>` Returns: `Map<NodeId, int>`	Computes shortest distances using integer weights. source : `NodeId` graph : `Graph<'n, int>` Returns: `Map<NodeId, int>`