Dijkstra Algorithm

Chào mừng bạn đến với "Kiệt tác" của lý thuyết đồ thị. Dijkstra chính là trái tim của Google Maps, Apple Maps và mọi thiết bị GPS.

Concept: GPS Navigation

Hãy tưởng tượng bạn đang ở TP.HCM (Source) và muốn đi Hà Nội (Target). Có hàng ngàn con đường và ngã rẽ. Dijkstra hoạt động như một nhà thám hiểm tham lam (greedy explorer):

1. Tại mỗi bước, nó luôn chọn đi đến thành phố gần nhất mà nó chưa chốt đường đi chính thức.
2. Từ thành phố mới đó, nó cập nhật lại khoảng cách đến các thành phố lân cận (nếu tìm thấy đường tắt ngắn hơn).

Cài Đặt Tối Ưu (Priority Queue)

Để đạt độ phức tạp O(E log V), bắt buộc phải dùng Min-Heap (Priority Queue). Nếu dùng mảng thường để tìm min, độ phức tạp sẽ là O(V^2), rất chậm!

Code Implementation

C++

#include <vector>
#include <queue>
using namespace std;

// Pair: {distance, node}
typedef pair<int, int> pii;

vector<int> dijkstra(int V, vector<vector<pii>> &adj, int src) {
    // 1. Khởi tạo khoảng cách vô cùng
    vector<int> dist(V, 1e9);
    dist[src] = 0;

    // Min-Heap lưu {distance, node}
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        // 🛑 HPN's Optimization: Lazy Deletion
        // Nếu khoảng cách lấy ra từ Heap lớn hơn khoảng cách hiện tại tốt nhất
        // -> Nghĩa là data này đã cũ (stale), bỏ qua!
        if (d > dist[u]) continue;

        for (auto &edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            // Relaxation Step
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Java

import java.util.*;

class Dijkstra {
    static class Node implements Comparable<Node> {
        int v, weight;
        Node(int v, int weight) { this.v = v; this.weight = weight; }
        public int compareTo(Node n) { return this.weight - n.weight; }
    }

    public int[] dijkstra(int V, ArrayList<ArrayList<Node>> adj, int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(src, 0)); // Trong Java PQ, ta dùng weight để sort

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.v;
            int d = node.weight;

            if (d > dist[u]) continue;

            for (Node neighbor : adj.get(u)) {
                if (dist[u] + neighbor.weight < dist[neighbor.v]) {
                    dist[neighbor.v] = dist[u] + neighbor.weight;
                    pq.add(new Node(neighbor.v, dist[neighbor.v]));
                }
            }
        }
        return dist;
    }
}

Python

import heapq

def dijkstra(V, adj, src):
    # adj is list of lists: adj[u] = [(v, weight), ...]
    dist = [float('inf')] * V
    dist[src] = 0
    
    # Min-Heap stores (distance, node)
    pq = [(0, src)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        # Optimization check
        if d > dist[u]:
            continue
            
        for v, weight in adj[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))
                
    return dist