Exploring Time Complexity of Dijkstra’s Algorithm in C++

Dijkstra's algorithm is a widely used algorithm for finding the shortest path between nodes in a weighted graph.

In this article, we will delve into the time complexity of Dijkstra's algorithm.

---

How Does Dijkstra's Algorithm Work?

Dijkstra's algorithm:

1. Starts from a source node.
2. Selects the node with the minimum distance that has not been visited yet.
3. Updates the distances of its neighbors.
4. Adds the neighbors to a priority queue.
5. Repeats this process until all nodes have been visited, finding the shortest path to each node from the source node.

int dijkstra(int src, int dest, vector<int>& path) {
    vector<int> distance(num_vertices + 1, INF);
    distance[src] = 0;
    vector<int> predecessor(num_vertices + 1);
    predecessor[src] = src;
    vector<bool> processed(num_vertices + 1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        int current_vertex = pq.top().second;
        pq.pop();
        if (processed[current_vertex]) {
            continue;
        }
        processed[current_vertex] = true;
 
        for (auto u : adj_list[current_vertex]) {
            int b = u.first, w = u.second;
            if ((distance[current_vertex] + w) < distance[b]) {
                distance[b] = distance[current_vertex] + w;
                pq.push({distance[b], b});
                predecessor[b] = current_vertex;
            }
        }
    }

    int curr = dest;

    while (true) {
        path.push_back(curr);
        if (predecessor[curr] == curr) {
            break;
        }
        curr = predecessor[curr];
    }
    reverse(path.begin(), path.end());
    return distance[dest];
}

---

Time Complexity

The time complexity the above program can be divided into following components:

1. Initialization

The initialization of the distance, predecessor, and processed vectors takes O(V) time, where V is the number of vertices.

2. Priority Queue Operations

The priority queue operations, including insertion and deletion, take O(logV) time per operation. Since we perform these operations V times, the total time complexity is O(VlogV).

3. Edge Updates

The edge updates take O(E) time, where E is the number of edges. This is because we iterate over all edges in the graph and update the distances and predecessors of the vertices.

Overall Time Complexity

The overall time complexity of the algorithm is the sum of the time complexities of the initialization, priority queue operations, and edge updates. Therefore, the overall time complexity is:

O(V) + O((V+E)log⁡V) + O(E) 

However, the logarithmic factor VlogV dominates the non-logarithmic factor V. This is because when V increases, the logarithmic term grows faster than the non-logarithmic factor V. Thus the overall time complexity becomes, O(VlogV + E).

Overall Time Complexity: O(VlogV + E)