Weighted Graphs

Bart Massey

Edge-weighted Graphs

  • Extend graph with a "labeling" function l: V -> Z+ that gives the "weight" of each edge of a graph.

      SINGLE-SOURCE SHORTEST PATH
    
      Given: A connected graph (V, E). A distinguished start
      node v0 in V. A set G of goal nodes with G a subset of
      V. A positive integer weight l(e) for every e in E.
    
      Find: A path p from v0 to vg for some vg in G with
      the sum of edge weights along the path minimal among
      all paths from v0 to some vg in G.
    

Dijkstra's Algorithm (Book)

  • Given graph (V, E) in adjacency-list form, start node v0, goal nodes G, weight function l:E->N

      if v0 in G
          return
      S <- new empty set
      D <- new empty dictionary
      for each edge (v0, w) in E
          D[v0] <- l(v0, w)
      loop
          T <- keys(P) \ S
          if T is empty
              fail
          v <- vertex in T minimizing P[v]
          if v in G
              return
          insert v into S
          for each edge (v, w) in E
              D[w] <- min(D[w], D[v] + l(v, w))
    
  • Correctness: Must terminate when every reachable node has been searched or a when a goal node is reached.

    Yields right answer by triangle property: see below.

  • Runtime: O(n2) by outer loop, minimization loop

Dijkstra's Algorithm ("Standard")

  • Given graph (V, E) in adjacency-list form, start node v0, goal nodes G, weight function l:E->N

      P <- new empty dictionary
      Q <- new empty priority queue
      S <- new empty set
      insert v0 into Q with priority 0
      while Q is not empty:
        extract min priority v from Q
        if v in G
          return path extracted from P, v
        insert v into S
        for w in neighbors of v
          if w not in S
            P[w] <- v
            insert w into Q with priority of v + l((v, w))
      fail
    
  • Run-time: O(|E|)

  • Correctness: Completes when all vertices have been examined.

    Soundness by contradiction. Imagine longer of two paths was selected. Now look at where the two paths converge for the final time. Must take last step of shorter path first.

All-Pairs Shortest Path

  • Might want to pre-build a map showing the shortest distance from any node to any other.

  • Can use Dijkstra's on each source vertex to build a VxV array of inter-node distances.

  • Given this table, one can reconstruct the path by moving from start to some goal by looking at the shortest total path from current node to neighbors.

      v <- v0
      P <- new empty sequence
      while v =/= g
          find neighbor w of v minimizing l(v, w) + D[w, g]
          append w to P
          v <- w
      return P
    
  • Can also construct a VxV array of parents for faster pathing.

  • There's another standard way to build the VxV table.

Floyd-Warshall Algorithm

  • Idea: Use intermediate nodes in some order to find shorter paths.

      D <- VxV matrix of distances, all "infinity"
      for (v, w) in E
          D[v, w] <- l(v, w)
      for k in V
          for i in V
              for j in V
                  d <- G[i, k] + G[k, j]
                  if d < G[i, j]
                      G[i, j] <- d
    
  • Correctness: Terminates. Every path transiting k is considered.

  • Running Time: O(n3), vs n calls to Dijkstra's.

  • Variant can compute "transitive closure" of a directed graph at a vertex.