We use Dijkstra algorithm to find the minimum distance from single srouce(src) to all other vertex in the given graph. It works only on Undirected Weighted Graph which are not having negative edge weights. It uses a greedy approach that repeatedly minimize the distances to other vertices.
We use priority queue to implement Dijkstra's algorithm.
The theory part you can learn on the Internet.
When we are using the visited array for the vertices that's distance from the src has already been finalized and not need to be evaluated again. This way it prevent the outdated entry from our queue to proceed furthur and continue the cycle to next valid vertice in the queue. So what happen is that when visiting the nbr we may have pushed a same node twice in the queue with different distance. because we are using priority queue the shorter one will get poped out first and the larger will be popped after that, but the time the larger will come in the picture the shorter one would already have marked the vertice as visited. Hence the larger one will not able to proceed after the visited check at line ****
vector<int> dijkstra(int V, vector<vector<pair<int,int>>>& adj, int src) {
vector<int> dist(V, INT_MAX);
vector<bool> visited(V, false);
dist[src] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, src});
while (!pq.empty()) {
auto [currDist, u] = pq.top();
pq.pop();
// Skip if already finalized ****
if (visited[u]) continue;
visited[u] = true;
for (auto [v, wt] : adj[u]) {
// Relax only unvisited neighbors
if (!visited[v] && currDist + wt < dist[v]) {
dist[v] = currDist + wt;
pq.push({dist[v], v});
}
}
}
return dist;
}
The second appraoch is based on the fact that when you will be having a same node in the priority queue twice the first will always be the one who will get popped out and will update the distance array with minimum distance. Now when the turn for the larger one will come we will put a check (in line ***** below) that I already have found a less distance than what you are suggesting now. Hence we can skip that entry of the queue and procedd with the remaining one in the queue.
vector<int> dijkstra(int V, vector<vector<pair<int,int>>>& adj, int src) {
vector<int> dist(V, INT_MAX);
dist[src] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, src});
while (!pq.empty()) {
auto [currDist, u] = pq.top();
pq.pop();
// Ignore outdated entries *****
if (currDist > dist[u]) continue;
for (auto [v, wt] : adj[u]) {
if (currDist + wt < dist[v]) {
dist[v] = currDist + wt;
pq.push({dist[v], v});
}
}
}
return dist;
}
Both of the implementation are correct and Just the difference is of the way you think. You can run some dry case or Can tell the AI to run step by step execution on a simple test case and will understand the gist of it.
take this test case: {u, v, wt} {0, 1, 10}, {0, 2, 1}, {1, 2, 1} src = 0