Dijkstra's Algorithm: Analysis

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(\text{neighbor}(v))$ to be $O(\deg(v))$. Repeating this $N$ times will give runtime of $O(M)$ for this part of the algorithm.

Let's focus on $O(?)$:

  • Finding (an unexplored) vertex with min distance is $O(N)$ if we store the "distances" in a linear data structure such as an array.
  • Since the above will be repeated $N$ times, it pushes the running time of algorithm to $O(N^2)$
  • You can use a priority queue (min-heap; priority is distance) to get $O(\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(?)$ is $O(\lg N)$ (using a [modified] priority queue), we get total running time of $O(M + N \lg N)$.