Finding the minimum weight Dijkstra tree

Question

Given a directed, weighted graph G=(V, E), running the Dijkstra algorithm can result in multiple shortest-path trees with different weights as seen in this picture where A is the source and D is the target. How can I create an algorithm that returns the Dijkstra tree with the least total weight in the same time it takes to run Dijkstra's algorithm (O(V+E)logV)?

wcochran wcochran · Accepted Answer · 2020-07-28T22:36:43

Usually you construct a tree while Dijkstra is running by tracking the optimal edge that leads into each node. For example, the prev[] array in the code below contains the tree by recording the optimal edge that leads into each node; i.e., the prev[] array contains the parent of each node in the tree:

 shortestPath(G, A, D, prev[])
      for v in G.V
          dist[v] = infinity
          prev[v] = -1 // no parent (assumes nodes are positive integers)
      dist[A] = 0
      for v in G.V
          Q.insert(v, dist[v])
      while Q not empty
          u = Q.deleteMin()
          if dist[u] >= infinity
              return false  // no path to u
          if u == D
              return true   // found path (don't stop if you want the whole tree)
          for all v adjacent to u
              let d = dist[u] + v.weight
              if d < dist[v]
                  dist[v] = d
                  prev[v] = u // update parent
                  Q.decreaseKey(v, d)

Since prev[] records the parent node of each tree you can find the optimal path by backtracking:

  v = D
  while v >= 0
     path.addFirst(v)
     v = prev[v]

In any case, prev[] holds the tree. If you want the tree in a different form you just need to post process prev[].

Finding the minimum weight Dijkstra tree

1 Answers