wire / wire-format / dijkstra

Dijkstra's shortest path algorithm

Dijkstra finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. Uses a priority queue (min-heap) of (distance, vertex). Greedy: always process the vertex with smallest tentative distance. Relax edges: if dist[u] + w(u,v) < dist[v], update dist[v]. O((V+E) log V) with binary heap, O(E + V log V) with Fibonacci heap.

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: Dijkstra's shortest path algorithm

wire format

spec: Dijkstra (1956)

Dijkstra finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. Uses a priority queue (min-heap) of (distance, vertex). Greedy: always process the vertex with smallest tentative distance. Relax edges: if dist[u] + w(u,v) < dist[v], update dist[v]. O((V+E) log V) with binary heap, O(E + V log V) with Fibonacci heap.

fieldsizemeaning
Priority queuemin-heapExtracts the vertex with smallest distance. O(log V) per extract/insert.
RelaxationO(1) per edgeIf dist[u] + w(u,v) < dist[v], update dist[v] and set predecessor.
Complexity (binary heap)O((V+E) log V)V extract-min + E decrease-key, each O(log V).
Complexity (Fibonacci heap)O(E + V log V)Amortized O(1) decrease-key, O(log V) extract-min.
A* (variant)heuristicA* adds a heuristic h(v) to the priority: f(v) = g(v) + h(v). Admissible heuristic (h(v) ≤ actual cost) guarantees optimality.

example:

00 00

Dijkstra (placeholder)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/dijkstra or /wire-format/dijkstra.json