SSSP II

Work in Progress

Concept

BFS for SSSP

  • add imaginary verticies

Dijkstra’s algorithm

Dijkstra(G, w, s):
    for each vertex v in G:
        d[v] = +∞
        parent[v] = ⊥
        count[v] = 0
    d[s] = 0
    count[s] = 1
    Q = priority queue containing each v with key d[v]
    while Q is not empty:
        u = ExtractMin(Q) 
        if d[u] = +∞:
            break
        for each v in Adj[u]:
            if v in Q and d[u] + w(u, v) < d[v]:
                d[v] = d[u] + w(u, v)
                parent[v] = u 
                DecreaseKey(Q, v, d[v])
    return (d, parent) 

min heap dijkstra vs array dijkstra

hidden heap version

Correctness
show that for all v in V, dist[v] = min distance of a path from s to v

base case: dist[s] = 0, positive weights, so no negative cycles

induction step: fix v, dist[v] >= delta(v)
for some u added to R before v, by IH
dist[v] = dist[u] + l_{uv}
= delta(u) + l_{uv}
>= delta(v)

dist[v] <= delta(v)
contradiction
for any other path from s-v there must be x in R and y not in R
such that s~>x->y~>v

means that l_{uv} <= l_{xy}
dist[y] >= dist[v]