Advanced Graph Algorithms: Dijkstra's Algorithm in C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <limits>
#include <unordered_set>

using namespace std;

typedef pair<int, int> pii;  // Pair to represent a node and its distance

unordered_map<char, unordered_map<char, int>> createGraph() {
    unordered_map<char, unordered_map<char, int>> graph;
    graph['A'] = {{ 'B', 1 }, { 'C', 4 }};
    graph['B'] = {{ 'A', 1 }, { 'C', 2 }, { 'D', 5 }};
    graph['C'] = {{ 'A', 4 }, { 'B', 2 }, { 'D', 1 }};
    graph['D'] = {{ 'B', 5 }, { 'C', 1 }};
    return graph;
}

unordered_map<char, int> dijkstra(unordered_map<char, unordered_map<char, int>> &graph, char start) {
    priority_queue<pii, vector<pii>, greater<pii>> min_heap;
    unordered_map<char, int> dist;
    unordered_set<char> visited;

    for (auto vertex : graph) {
        dist[vertex.first] = numeric_limits<int>::max();  // Initial distances are infinity
    }
    dist[start] = 0;
    min_heap.push({ 0, start });  // Push the start node with distance 0

    while (!min_heap.empty()) {
        char u = min_heap.top().second;
        min_heap.pop();

        if (visited.find(u) != visited.end()) {
            continue;
        }
        
        visited.insert(u);

        for (auto &neighbor : graph[u]) {
            char v = neighbor.first;
            int weight = neighbor.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                min_heap.push({ dist[v], v });
            }
        }
    }

    return dist;
}

int main() {
    auto graph = createGraph();
    char start = 'A';
    auto distances = dijkstra(graph, start);

    for (auto &dist : distances) {
        cout << "Distance from " << start << " to " << dist.first << " is " << dist.second << endl;
    }

    // Output:
    // Distance from A to A is 0
    // Distance from A to B is 1
    // Distance from A to C is 3
    // Distance from A to D is 4

    return 0;
}