Shortest Path

Algorithm สำหรับหาเส้นทางสั้นที่สุด: Dijkstra, Bellman-Ford, Floyd-Warshall

Shortest Path Algorithms

การหาเส้นทางสั้นที่สุดเป็นปัญหาพื้นฐานที่พบบ่อยในการแข่งขัน มี algorithm หลายตัวที่เหมาะกับสถานการณ์ต่างกัน

Overview

Algorithm	Graph Type	Complexity	ใช้สำหรับ
BFS	Unweighted	$O(V+E)$	Edge weight = 1
Dijkstra	Non-negative weights	$O((V+E) \log V)$	Single source
Bellman-Ford	Any weights	$O(VE)$	Negative weights
Floyd-Warshall	Any weights	$O(V^3)$	All pairs

Dijkstra’s Algorithm

หา shortest path จาก single source ไปยังทุก vertex ใน graph ที่มี non-negative edge weights

Algorithm

กำหนด distance ของ source = 0, ที่เหลือ = $\infty$
ใช้ priority queue เก็บ (distance, vertex)
ดึง vertex ที่มี distance น้อยที่สุด
Update distance ของ neighbors (relaxation)
ทำซ้ำจนกว่า priority queue จะว่าง

Implementation

const int INF = 1e9;

vector<int> dijkstra(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<int> dist(n, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue; // Skip outdated entries
        
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

Dijkstra กับ Path Reconstruction

pair<vector<int>, vector<int>> dijkstraWithPath(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<int> dist(n, INF);
    vector<int> parent(n, -1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
    
    return {dist, parent};
}

vector<int> getPath(int end, vector<int>& parent) {
    vector<int> path;
    for (int v = end; v != -1; v = parent[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

Complexity

Time: $O((V + E) \log V)$ with priority queue
Space: $O(V)$

Bellman-Ford Algorithm

หา shortest path จาก single source และรองรับ negative edge weights พร้อมตรวจจับ negative cycle

Algorithm

กำหนด distance ของ source = 0, ที่เหลือ = $\infty$
ทำ relaxation ทุก edges ทั้งหมด $V-1$ รอบ
ตรวจสอบ negative cycle (ถ้า relax ได้อีกแสดงว่ามี)

Implementation

struct Edge {
    int u, v, w;
};

vector<int> bellmanFord(int start, int n, vector<Edge>& edges) {
    vector<int> dist(n + 1, INF);
    dist[start] = 0;
    
    // Relax V-1 times
    for (int i = 0; i < n - 1; i++) {
        for (auto& e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
            }
        }
    }
    
    // Check for negative cycle
    for (auto& e : edges) {
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
            // Negative cycle detected
            return {}; // หรือจัดการตามโจทย์
        }
    }
    
    return dist;
}

Bellman-Ford กับ Negative Cycle Detection

bool hasNegativeCycle(int n, vector<Edge>& edges) {
    vector<int> dist(n + 1, 0); // เริ่มจาก 0 ทุก vertex
    
    for (int i = 0; i < n; i++) {
        bool updated = false;
        for (auto& e : edges) {
            if (dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
                updated = true;
            }
        }
        if (!updated) break;
    }
    
    // ถ้า update ได้ในรอบที่ n แสดงว่ามี negative cycle
    for (auto& e : edges) {
        if (dist[e.u] + e.w < dist[e.v]) {
            return true;
        }
    }
    return false;
}

Complexity

Time: $O(VE)$
Space: $O(V)$

Floyd-Warshall Algorithm

หา shortest path ระหว่าง ทุกคู่ ของ vertices

Algorithm (Dynamic Programming)

$dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j])$

โดย $k$ คือ intermediate vertex

Implementation

void floydWarshall(vector<vector<int>>& dist) {
    int n = dist.size();
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

Setup และ Usage

int main() {
    int n, m;
    cin >> n >> m;
    
    // Initialize
    vector<vector<int>> dist(n, vector<int>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    
    // Read edges
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w); // if undirected
    }
    
    floydWarshall(dist);
    
    // dist[i][j] = shortest path from i to j
}

Detecting Negative Cycle

bool hasNegativeCycleFloyd(vector<vector<int>>& dist) {
    floydWarshall(dist);
    int n = dist.size();
    
    for (int i = 0; i < n; i++) {
        if (dist[i][i] < 0) return true;
    }
    return false;
}

Path Reconstruction

vector<vector<int>> next_node;

void floydWarshallWithPath(vector<vector<int>>& dist) {
    int n = dist.size();
    next_node.assign(n, vector<int>(n, -1));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] != INF && i != j) {
                next_node[i][j] = j;
            }
        }
    }
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        next_node[i][j] = next_node[i][k];
                    }
                }
            }
        }
    }
}

vector<int> getPathFloyd(int u, int v) {
    if (next_node[u][v] == -1) return {}; // No path
    
    vector<int> path = {u};
    while (u != v) {
        u = next_node[u][v];
        path.push_back(u);
    }
    return path;
}

Complexity

Time: $O(V^3)$
Space: $O(V^2)$

SPFA (Shortest Path Faster Algorithm)

เวอร์ชันเร็วกว่าของ Bellman-Ford (average case)

vector<int> spfa(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<int> dist(n, INF);
    vector<bool> inQueue(n, false);
    queue<int> q;
    
    dist[start] = 0;
    q.push(start);
    inQueue[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
    
    return dist;
}

Complexity: $O(VE)$ worst case, แต่มักจะเร็วกว่าในทางปฏิบัติ

เลือกใช้ Algorithm ไหน?

กราฟเป็นอย่างไร?
│
├── Edge weights = 1 (หรือไม่มี)
│   └── BFS O(V+E)
│
├── Non-negative weights
│   ├── Single source → Dijkstra O((V+E)log V)
│   └── All pairs → Floyd-Warshall O(V³) หรือ Dijkstra V ครั้ง
│
└── มี negative weights
    ├── ตรวจ negative cycle → Bellman-Ford O(VE)
    └── All pairs → Floyd-Warshall O(V³)

ตัวอย่างโจทย์

โจทย์: หา Shortest Path ระหว่างสอง Node

int main() {
    int n, m, start, end;
    cin >> n >> m >> start >> end;
    
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w}); // undirected
    }
    
    auto dist = dijkstra(start, adj);
    
    if (dist[end] == INF) {
        cout << -1 << endl; // ไม่มีทาง
    } else {
        cout << dist[end] << endl;
    }
}

สรุป

สถานการณ์	Algorithm
Unweighted graph	BFS
Non-negative weights, single source	Dijkstra
Negative weights, single source	Bellman-Ford / SPFA
All pairs, small V	Floyd-Warshall
Detect negative cycle	Bellman-Ford

💡 Tip: ถ้า graph มี edge weight เป็น 0 หรือ 1 ใช้ 0-1 BFS จะเร็วกว่า Dijkstra