Dijkstra's Algorithm

On Sparse Graph (binary heap as pq)

This implementation has time complexity of $O(E\,log\,E)$, which is suitable for sparse graph ($E \ll V^2$).

void dijkstra(int src)
{
    fill(min_d, min_d+N, INF);
    fill(prev, prev+N, -1)
    min_d[src] = 0;
    priority_queue< pii, vector<pii>, greater<pii> > pq;
    pq.push({0, src});

    while ( !pq.empty() ) {
        int v = pq.top().second, d_v = pq.top().first;
        pq.pop();
        if ( d_v != min_d[v] ) continue;
        for ( auto e : adj[v] ) {
            int to = e.second, wei = e.first;
            if ( d_v + wei < min_d[to] ) {
                min_d[to] = min_d[v] + wei;
                prev[to] = v;
                pq.push( {min_d[to], to} );
            }
        }
    }
}

On Dense Graph (array as pq)

This implementation has time complexity of $O(V^2)$, which is suitable for dense graph ($E \approx V^2$). The only difference between this algorithm and the previous one is the implementation of priority queue.

void dijkstra(int src)
{
    fill(min_d, min_d+N, INF);
    fill(prev, prev+N, -1);
    fill(used, used+N, false);
    min_d[src] = 0;

    for ( int i = 0; i < N; i++ ) {
        int v = -1;
        for ( int j = 0; j < N; j++ )
            if ( !used[j] && (v == -1 || min_d[j] < min_d[v]) )
                v = j;

        if ( min_d[v] == INF )
            break;

        used[v] = true;
        for ( auto e : adj[v] ) {
            int to = e.second, wei = e.first;
            if ( min_d[v] + wei < min_d[to] ) {
                min_d[to] = min_d[v] + wei;
                prev[to] = v;
            }
        }
    }
}