# graphs : paths

weighted   sssp   Dijkstra   snapshot   time   minheap   buildheap   time   negative

## single source shortest path

• input: graph/digraph, non-negative edge/arc weights, start node s

• output: for each node v, shortest path from s to v

## Dijkstra's sssp algorithm

• here

• includes proof of correctness

Dijkstra sssp example
```dist         parent     fringe pick
A B C D E    A B C D E
0 . . . .    A . . . .   A     A
0 4 2 . .    A A A . .   BC    C
0 3 2 6 7    A C A C C   BDE   B
0 3 2 5 6    A C A B B   DE    D
0 3 2 5 6    A C A B B   E     E
```
Dijkstra's sssp algorithm (simple version)
```dist[s] == 0    fringe = { s }
while not isempty(fringe):
v = a fringe vertex with min dist
remove v from fringe
for each nbr w of v:
newdist = dist[v] + wt(v,w)
if newdist < dist[w]:
dist[w] = newdist    parent[w] = v
```
simple Dijkstra (no priority queue)
```def weightSum(G):
sum = 0
for u in G:
for (v,weight) in G[u]: sum += weight
return sum

def showAll(G,D,P):
print '\nprnt',
for v in sorted(G): print P[v],
print '\nnode',
for v in sorted(G): print v,
print '\ndist',
for v in sorted(G): print D[v],
print ''

def showFringe(G,F,D,inf):
print '  fringe',
for v in sorted(F):
if D[v]!=inf:
print v,D[v],' ',

def sssp(G,start):
infinity = 999 + weightSum(G)
dist, parent, fringe = {}, {}, []
for v in G:
dist[v], parent[v] = infinity, -1
fringe.append(v)
dist[start],parent[start] = 0, start

doneEarly = False
while len(fringe)>0 and not doneEarly:
showFringe(G,fringe,dist,infinity)
ndxMin = 0
for j in range(1,len(fringe)):
if dist[fringe[j]] < dist[fringe[ndxMin]]: ndxMin = j
u = fringe.pop(ndxMin)
print '\npick',u,':',
if (dist[u] == infinity): doneEarly = True
for (v,duv) in G[u]:
if dist[v] > dist[u] + duv:
dist[v] = dist[u] + duv
parent[v] = u
print v,dist[v],' ',
print ''
showAll(G,dist,parent)

G = {'A': [['B',4],['C',2]],
'B': [['C',3],['D',2],['E',3]],
'C': [['B',1],['D',4],['E',5]],
'D': [],
'E': [['D',1]]}
sssp(G,'A')
```

## Dijkstra (no priority queue) runtime

• n nodes removed from fringe

• updating distance values when node v removed from fringe takes Θ(degree v) time

• each vertex removed from fringe once, so total Θ(m) time

• finding node to remove from fringe takes Θ(k) time, where k is number of nodes in fringe, so total &Theta(n2) time

• so total Θ(m + n2) = Θ(n2) time

can we do better ?
• yes, if we can use priority queue: allows updates and deletemins in o(n2) time

• first improvement: implement PQ with binary minheap

• better: implement PQ with Fibonacci heap (not in this course)

## binary minheap

• wiki

• n nodes, each with key, stored in array

• array represents a complete binary tree

• for node

• parent

• left child

• right child

• min-heap property

• for each node v with a parent, key(parent(v)) <= key(v)

• warning: text uses array indices

minheap operations
```H[] is minheap, n is number items in H

trickledown(H,n,j):
while haschild(j) and out-of-order(j, minchild(j)):
newj <- index of smaller child
swap(node(j), node(newj))
j <- newj

bubbleup(H,n,j):
while hasparent(j) and out-of-order(parent(j), j):
newj <- index of parent
swap(node(newj), node(j))
j <- newj

insert(H,n,x):
n <- n+1
H[n] <- x
bubbleup(n)

decreasekey(H,n,j, x):
H[j] <- x
bubbleup(j)

deletemin(H,n):
m <- H[0]
H[0] <- H[n-1]
n <- n-1
trickledown(H,n,0)

buildheap(H,n):
for j in range(n):
H[j] <- new node
bubbleup(j)

buildheapfast(H,n):
for j in range(n):  H[j] <- new node
for j in range(0, (n-2)/2, -1): # descending order
trickledown(j)
```

## buildheap time/correctness

bubbleup buildheap demo
```for j: 1 .. n-1: bubbleup(j)

array: 4 7 2 1 6 9 5 3 0 8
compact binary tree:
4
7              2
1     6        9     5
3 0   8

bubbleup(1)
4
7              *
*     *        *     *
* *   *

bubbleup(2)
2
*              4
*     *        *     *
* *   *

bubbleup(3)
1
2              *
7     *        *     *
* *   *

bubbleup(4)
*
2              *
*     6        *     *
* *   *

bubbleup(5)
*
*              4
*     *        9     *
* *   *

bubbleup(6)
*
*              4
*     *        *     5
* *   *

bubbleup(7)
*
*              *
3     *        *     *
7 *   *

bubbleup(8)
0
1              *
2     *        *     *
* 3   *

bubbleup(9)
*
*              *
*     6        *     *
* *   8

minheap
0
1              4
2     6        9     5
7 3   8

array: 0 1 4 2 6 9 5 7 3 8
```
trickledown buildheap demo
```for j: n/2 .. 0: trickledown(j)

start:
4
7            2
1     6      9     5
3 0   8

trickledown(4)
*
*            *
*     6      *     *
* *   8

trickledown(3)
*
*            *
0     *      *     *
3 1   *

trickledown(2)
*
*            2
*     *      9     5
* *   *

trickledown(1)
*
0            *
1     6      *     *
3 7   *

trickledown(0)
0
1            2
3     6      *     *
4 7   *

minheap
0
1            2
3     6      9     5
4 7   8

array: 0 1 2 3 6 9 5 4 7 8
```
bubbleup buildheap: wc key compares, n=31
```                          *
1                             1
2             2               2             2
3     3       3     3         3     3       3     3
4 4   4 4     4 4   4 4       4 4   4 4     4 4   4 4
```
bubbleup buildheap worst case time
• bup(1) bup(2) bup(3) … bup(n-1)

• worst case: each bup goes to root

• wc kc

• Σ(j: 2 to n) ⌊ lg j ⌋

• ∈ Θ(n log n)

trickledown buildheap wc kc, n=31
```                          4
3                             3
2             2               2             2
1     1       1     1         1     1       1     1
* *   * *     * *   * *       * *   * *     * *   * *
```
```n=3   1                                      = 3-2
n=7   1+1  +2                                = 7-3
n=15  1+1+1+1 +2+2 + 3                       = 15-4
n=31  1+1+1+1+1+1+1+1 +2+2+2+2 + 3+3  + 4    = 31-5
n=2^t-1   2^{t-1} + 2(2^{t-2}) + 3(2^{t-3}) + ... + (t-2)(2^1) + (t-1)2^0
```
n = 31, above sum, as picture
```sum 1*8 + 2*4 + 3*2 + 4*1 represented by
8A, 8B, 6C, 4D.  notice sum is 16+15-5 = 26

*
D                *
C C              D *
B B B B          C C D *
A A A A A A A A  B B B B C C D *
```
trickledown buildheap worst case time
• td(n/2) td(n/2 -1) td(n/2 -3) … td(0)

• worst case: each trickledown goes to leaf

• simplifying assumption: n = 2k-1

• wc kc

• 2 * ( 1*2k-2 + 2*2k-3 + 3*2k-4 + ... + (k-1)*2k-k )

• 2k+1 Σ(j: 1 to k-1)   j / 2j+1

• 2k+1 Σ(j: 1 to k-1)   j / 2j+1

• 2k+1 (1 - (k+1)/2k ) = 2(2k - (k+1))

• ∈ Θ(n)

bubbleup buildheap correctness
• claim: after bup(j), array[0 1 2 .. j] is a minheap

• argue by induction

• assume after bup(j-1), array]1 … j-1] is a minheap

• now we call bup(j)

• case: key[ parent(j) ] ≤ key[ j ]

• now every node satisfies the heap property, we are done

• case: key[ parent(j) ] > key[ j ]

• now we swap these two, and since before the swap key[ parent(j) ] was no greater than the key of any other child, and we have made it smaller, it is still no greater than the key of any other child. continue arguing in this fashion if we bubbleup from parent(j).

```                          2
5                             8
8             7               ?             *
*     *       *     *         *     *       *     *
```

## Dijkstra, with minheap, runtime

minheap operation runtimes
• trickledown, bubbleup, insert, decreasekey WC Θ(log n)

• buildheap WC Θ(n log n)

• buildheapfast WC Θ(n)

Dijkstra, with minheap, runtime
• buildheapfast Θ(n)

• n extractmins: Θ(n log n)

• m decreasekeys: Θ(m log n)

• total Θ((m+n) log n) = Θ(m log n)

• with Fibonacci heap, Θ(m + n log n)

## negative weights

• if neg wt edges and reachable neg wt cycle, then no sssp solution

• if neg wt edges but no neg wt cycles, Bellman-Ford solves sssp

Bellman-Ford
```def infinity(): return 999
def myprint(d):
if d==infinity(): print '--',
else: print '%2s' % d,

def update(x,y,dxy,D,P):
change = 0
if D[x]<infinity() and D[y] > D[x] + dxy:
D[y], P[y], change = D[x] + dxy, x, 1
return change

def sssp(G,source):
dist, parent = {}, {}
for v in G:
dist[v], parent[v] = infinity(), -1
dist[source],parent[source] = 0, source

print 'from',source,'  ',
for v in sorted(G): print '%2s' % v,
print '\ndistance ',
for v in sorted(G): myprint(dist[v])

for _ in range(len(G)-1):
for v in G:
for (w,dvw) in G[v]:
print '\ndistance ',
for v in sorted(G): myprint(dist[v])

print '\nparent   ',
for v in sorted(G): print '%2s' % parent[v],
print ''

G = {'A': [['E',2]],
'B': [['A',1],['C',1]],
'C': [['D',3]],
'D': [['E',-1]],
'E': [['B',-2]],
'F': [['A',-4],['E',-1]],
'G': [['F',1]],
'S': [['A',10],['G',8]]}
sssp(G,'S')
```