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

Lesson Overview

Welcome to this insightful practice-based lesson! Today, we are diving deep into Advanced Graph Algorithms. Trust me, this is an all-important topic in computer science as graphs are prevalent in numerous real-world situations, from social networks to computer networks.

Understanding how to traverse, search, and optimize graphs is crucial, particularly when it comes to finding the shortest path between nodes, mapping routes, or determining any associations between specific data points. Let's go!

Introduction to Dijkstra’s Algorithm

One of the exciting algorithms we'll be examining is Dijkstra’s Algorithm. Named after its Dutch computer scientist inventor, Dijkstra's algorithm is a cornerstone for finding the shortest path in a graph with non-negative weights. The algorithm centers on a priority queue represented as a binary heap, which ensures that at any given point, the unvisited node with the lowest distance is chosen. The algorithm keeps track of the shortest distance from the start node to all other nodes in the graph, progressively updating the shortest distance for only the unvisited nodes.

Here is the implementation of the algorithm:

#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;
}
Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal