Dijkstra's Algorithm: Analysis

  • Analyze the running time of Dijkstra's algorithm, assuming an incidence/adjacency list Graph implementation.
  • Describe the role of support data structures in reducing the running time of Dijkstra's algorithm from quadratic to log-linear.

Here is the Dijkstra's Algorithm for finding shortest path: 

for each vertex v
    distance[v] = Infinity
    previous[v] = null
    explored[v] = false
distance[s] = 0   // s is the source
repeat N times
    let v be unexplored vertex with smallest distance
    explored[v] = true
    for every u: unexplored neighbor(v)
        d = distance[v] + weight[v,u]  
        if d < distance[u]
            distance[u] = d
            previous[u] = v

Exercise Analyze the complexity of SPF algorithm (use Big-Oh notation).

Solution 
for each vertex v            // O(N)
    distance[v] = Infinity      // O(1)
    previous[v] = null          // O(1)
    explored[v] = false         // O(1)
distance[s] = 0              // O(1)
repeat N times               // O(N)
    let v be unexplored vertex with smallest distance  // O(?)
    explored[v] = true          // O(1)
    for every u: unexplored neighbor(v)  // O(neighbor(v))
        d = distance[v] + weight[v,u]       // O(1)
        if d < distance[u]                  // O(1)
            distance[u] = d                 // O(1) 
            drevious[u] = v                 // O(1)

Using incidence/adjacency list representation will make O(neighbor(v))\Omicron(\text{neighbor}(v)) to be O(deg⁡(v))\Omicron(\deg(v)). Repeating this NN times will give runtime of O(M)\Omicron(M) for this part of the algorithm.

Let's focus on O(?)\Omicron(?):

  • Finding (an unexplored) vertex with min distance is O(N)\Omicron(N) if we store the "distances" in a linear data structure such as an array.
  • Since the above will be repeated NN times, it pushes the running time of the algorithm to O(N2)\Omicron(N^2)
  • You can use a priority queue (min-heap; priority is distance) to get O(lg⁡N)\Omicron(\lg N) on finding (an unexplored) vertex with min distance.
  • But you must also update the distances! How can you do that in Priority Queue? (This is left unanswered - you need it for HW8!)

If O(?)\Omicron(?) is O(lg⁡N)\Omicron(\lg N) (using a [modified] priority queue), we get total running time of O(M+Nlg⁡N)\Omicron(M + N \lg N).