0%

Dijkstra

Dijkstra Algorithm is the known fastest algorithm to find the shortest path in a graph with unbounded non-negative weights.

Time Complexity: E + V*log(V)

  • E is the number of edges
  • V is the number of vertexs

Implementation

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#!/usr/local/bin/python3

from typing import List
from collections import defaultdict
import heapq
import math

def dijkstra(vertexs: int, edges: List[List[int]], origin: int, destination: int):
'''
print shortest path from origin to destination
Args:
vertexs: number of vertexs. First vertex is 0.
edges: list of (start, end, weight)
origin: -
destination: -
Raise:
ValueError: if destination is not reachable from origin
'''
graph = defaultdict(dict)
# build graph
for u, v, w in edges:
graph[u][v] = w
# prepare data
dist, prev = defaultdict(lambda: math.inf), [None] * vertexs
dist[origin] = 0
heap = [(0, origin)]
# relax edges
while heap:
_, u = heapq.heappop(heap)
for v, w in graph[u].items():
# if neighbor is not reachable or find a shorter path
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
# build path
path, cur = [], destination
while cur != origin and prev[cur] is not None:
path.append(cur)
cur = prev[cur]
if cur != origin:
raise ValueError(f'{destination} is not reachable from {origin}')
path = [origin] + path[::-1]
print('->'.join([str(point) for point in path]))

dijkstra(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]], 0, 4)

C++

Dijkstra C++

Test Case

1
2
3
4
5
6
7
8
9
10
11
          +-+                  +-+
+-2----->+1| |4+<--+
| +++ +++ |
+++ | +-+ ^ |
|0| +--3----->+3+----3---+ |
+++ +-+ |
| +-+ |
+--5---->+2+----------------10------+
+-+

0->1->3->4