Dijkstra's Algorithm

Finds shortest distances between source and other nodes in $O (n^{2})$
$d [v]$ for each $v$ with length of shortest path from $s$ to $v$
- Initially, $d [s]$ is 0, other vertices have length of infinity
Boolean array $u [v]$ for each $v$ which stores if $v$ is marked
At each iteration, unmarked $v$ with lowest $d [v]$ is picked
- In first iteration, starting $s$ is selected
- Selected vertex $v$ is marked in $u [v]$
- From $v$ , relaxations are performed to reduce distance
  - For each edge of form $(v, t o)$ , algorithm tries to improve $d [t o]$
  - If length of current edge is $l e n$ , relaxation is $d [t o] = min (d [t o], d [v] + l e n)$
- After $n$ iterations, all vertices will be marked
Values are the shortest paths, infinite values are unreachable

import math
 
# nodes
nodes = [
    [(1, 5), (2, 10), (5, 15)],
    [(5, 5)],
    [(3, 2)],
    [], [], [],
]
n = len(nodes)
 
# distances
d = [math.inf if i != 0 else 0 for i in range(n)]
 
# markings
u = [False for _ in range(n)]
 
# parents
p = [-1 for _ in range(n)]
 
for _ in range(n):
    v = None
 
    # find lowest v which is unmarked
    for i, vd in enumerate(d):
        if not u[i] and (v == None or vd < d[v]):
            v = i
 
    u[v] = True
 
    # iterate over edges
    for edge in nodes[v]:
        to = edge[0]
        length = edge[1]
 
        # set new distance if lower
        if d[v] + length < d[to]:
            d[to] = d[v] + length
            p[to] = v
 
print(d)
print(p)

ayukmr

Explorer

Dijkstra's Algorithm

Graph View