Dijkstra

What is Dijkstra

Dijkstra is used to solve the single source shortest path question, which based on the greedy algorithm. The core idea is similar to the Prim algorithm.

The difference between it and Prim

Dijkstra’s algorithm and Prim’s algorithm are quite similar; they differ primarily only in their condition for adding nodes to the priority queue.Dijkstra’s is a Shortest Path algorithm. Since a node may have a path of shorter total length from the source, even if it has been “visited” (i.e., its shortest known path is updated), it may still need to be processed again.Prim’s solves the Minimum Spanning Tree (MST) problem, where our only goal is to connect all nodes, and there is no specific destination. Once a node is marked as visited in Prim’s, it implies two things: first, an edge with a smaller weight has certainly been extracted and connected to it; and second, the weight of any other edge connecting another node to the currently processed node must be greater than the weight of the already stored edge (which is the shortest edge connecting the MST to the new node).The reason for marking a node as “visited” in Dijkstra’s (when using a standard implementation) is that, according to the minimum-heap ordering rule, a shorter path to that node must have already been extracted from the priority queue. However, a still shorter path might exist later on and update the distance of arriving this node.Dijkstra’s algorithm requires maintaining the shortest path to every node, initially set to $\text{INT_MAX}$. For example, if the path from $1 \to 2$ is 3, then $\text{dist}[2] = 3$. But if the total path $1 \to 3 \to 2$ is 2, then we update the shortest path for $1 \to 2$ to 2 (i.e., $\text{dist}[2] = 2$). This is called the Relax operation. By relaxing all nodes, we can find the shortest path from the starting node to the destination, meaning $\text{dist}[\text{end}] = \text{shortest}$.

c++ Inplement

vector<vector<pair<int, int>>>adj;
void init(void)
{
    adj = vector<vector<pair<int, int>>>(1000);
}

int Dijkstra(int start, int end)
{
    vector<bool> visit(1000, false);
    vector<int> dist(1000, INT_MAX);
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>>pq;
    pq.push({0, start});
    while(!pq.empty())
    {
        auto[d, u] = pq.top(); pq.pop();
        if(visit[u]) continue;
        visit[u] = true;
        if(u == end) break;
        for(auto [v, w] : adj[u])
        {
            if(dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist[end];
}

To summarize the condition for adding nodes to the priority queue in both algorithms:

• Prim’s checks whether the node has been visited and only compares the edge weight ($\text{dist}[v] > w$).

• Dijkstra’s must compare the currently stored minimum distance to that point with the newly discovered path distance ($\text{dist}[v] > \text{dist}[u] + w$).

The limitations of Dijkstra

Dijkstra’s algorithm inherently assumes that once a node is popped from the priority queue, the shortest distance to that node is finalized and will not be updated again. This assumption holds true if all edge weights are non-negative. However, if negative edge weights exist, there might be a path—-for example, one involving a sufficiently short edge (like $-100,000$) that hasn’t been processed yet—-that connects to this already-popped node. In such a scenario, a shorter path to that node exists, and the algorithm fails to find the true shortest path.Therefore, Dijkstra’s algorithm：

• Can not solve the Negative Edge Weights.

• Can not solve the Negative Weight Cycles.

• Only a single source.

Time Complexity