graphs : paths

weighted   sssp   Dijkstra   snapshot   time   minheap   buildheap   time   negative  

weighted graphs/digraphs

a weighted digraph D

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

a weighted digraph D

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:
    add w to fringe (if not there already)
    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 snapshot

Dijkstra sssp snapshot

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 H[0 ldots n-1]

  • array represents a complete binary tree

  • for node H[j]

    • parent H[ : : lfloor (j-2)/2 rfloor : : ]

    • left child H[: : 2*j+1 : : ]

    • right child H[: : 2*j+2 : : ]

  • min-heap property

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

  • warning: text uses array indices 1 ldots n

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):
    updates = 0
    for v in G:
      for (w,dvw) in G[v]:
        updates += update(v,w,dvw,dist,parent)
    print '\ndistance ',
    for v in sorted(G): myprint(dist[v])
    if updates==0: break

  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')