wire / wire-format / dijkstra
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.
aka: Dijkstra's shortest path algorithm
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.
| field | size | meaning |
|---|---|---|
| Priority queue | min-heap | Extracts the vertex with smallest distance. O(log V) per extract/insert. |
| Relaxation | O(1) per edge | If 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) | heuristic | A* 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)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/dijkstra
or /wire-format/dijkstra.json