I implemented Dijkstra's algorithm using only a FIFO queue, still it passes all test cases in GFG. When will this code fail or if it works then why do we need to use a min heap?
vector <int> dijkstra(int V, vector<vector<int>> adj[], int S)
{
// adj [] = {{{1, 9}}, {{0, 9}}}
vector<int> dist(V, INT_MAX);
queue<pair<int, int>> pq;
pq.push({0, S});
while(!pq.empty()) {
auto f = pq.front();
pq.pop();
int node = f.second;
int d = f.first;
if (d < dist[node])
{
dist[node] = d;
for(auto i: adj[node]) {
pq.push({d + i[1], i[0]});
}
}
}
return dist;
}
Using a FIFO instead of a min-heap will still give you the correct answer, but the time that your program will take to find that answer will be longer.
To be noticeable, you would need to provide a large graph as input.