Thuật toán Dijkstra
Cập nhật lần cuối
Thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong đồ thị có trọng số cạnh không âm. Thuật toán lưu một khoảng cách tạm thời cho mỗi đỉnh, liên tục chốt đỉnh chưa chốt có khoảng cách tạm thời nhỏ nhất, rồi nới lỏng các cạnh của nó: cập nhật khoảng cách của một đỉnh kề mỗi khi tìm thấy đường đi ngắn hơn qua đỉnh hiện tại. Nhấn Phát ở trên để xem các khoảng cách giảm dần khi từng đỉnh được chốt.
Ý tưởng cốt lõi là tham lam: khi đã chọn đỉnh chưa chốt gần nhất, khoảng cách của nó là cuối cùng, vì mọi đường khác đến nó đều phải đi qua một đỉnh vốn đã xa hơn. Với hàng đợi ưu tiên dùng binary heap, Dijkstra chạy trong thời gian O((V + E) log V). Thuật toán yêu cầu trọng số không âm: hãy dùng Bellman-Ford nếu cạnh có thể âm.
Độ phức tạp thời gian và không gian
| Cách cài đặt | Độ phức tạp | Ghi chú |
|---|---|---|
| Binary heap | O((V + E) log V) | Lựa chọn phổ biến và thực tế |
| Duyệt mảng | O(V²) | Đơn giản hơn; ổn với đồ thị dày |
| Không gian | O(V) | Khoảng cách + hàng đợi ưu tiên |
| Yêu cầu | Trọng số không âm | Cạnh âm phá vỡ lựa chọn tham lam |
Từng bước thực hiện
| Bước | Điều gì xảy ra |
|---|---|
| 1 | Đặt khoảng cách của đỉnh nguồn là 0 và của mọi đỉnh khác là vô cùng. |
| 2 | Chọn đỉnh chưa chốt có khoảng cách tạm thời nhỏ nhất. |
| 3 | Đánh dấu đã chốt: khoảng cách ngắn nhất của nó giờ là cuối cùng. |
| 4 | Với mỗi đỉnh kề, tính khoảng cách qua đỉnh hiện tại + trọng số cạnh. |
| 5 | Nếu giá trị đó nhỏ hơn khoảng cách hiện tại của đỉnh kề, nới lỏng nó. |
| 6 | Lặp lại cho đến khi mọi đỉnh đến được đều đã được chốt. |
Ví dụ minh họa
Đường đi ngắn nhất từ đỉnh nguồn A trên đồ thị với các cạnh A-B=4, A-C=1, C-B=2, C-D=5, B-D=1:
| Bước | Chốt | Khoảng cách | Thao tác |
|---|---|---|---|
| 0 | - | A=0, B=∞, C=∞, D=∞ | Khởi tạo: đỉnh nguồn A=0, mọi đỉnh khác là vô cùng. |
| 1 | A (0) | B=4, C=1, D=∞ | Nới lỏng các cạnh từ A: đặt B=4, C=1. |
| 2 | C (1) | B=3, D=6 | Qua C: B=1+2=3 tốt hơn 4; D=1+5=6. |
| 3 | B (3) | D=4 | Qua B: D=3+1=4 tốt hơn 6. |
| 4 | D (4) | A=0, C=1, B=3, D=4 | Chốt D; không còn gì để nới lỏng. Xong. |
Khi nào nên dùng thuật toán Dijkstra
| Nên dùng khi | Tránh dùng khi |
|---|---|
| Mọi trọng số cạnh đều không âm | Có cạnh có thể âm: hãy dùng Bellman-Ford |
| Bạn cần đường đi ngắn nhất từ một nguồn đến mọi đỉnh | Bạn cần đường đi ngắn nhất giữa mọi cặp đỉnh: Floyd-Warshall đơn giản hơn |
| Đồ thị có trọng số và bạn muốn khoảng cách chính xác | Đồ thị không trọng số: BFS thông thường nhanh và đơn giản hơn |
| Bạn có sẵn một heap/hàng đợi ưu tiên tốt | Bạn muốn nhanh chóng đến một đích duy nhất bằng heuristic: hãy dùng A* |
Code Dijkstra's Algorithm
Một cách cài đặt Dijkstra's Algorithm gọn gàng, chạy được ngay bằng Python, JavaScript, Java, C++, C. Chọn một ngôn ngữ, sao chép code hoặc mở sẵn trong Coddy Playground.
Code Dijkstra's Algorithm bằng Python
1import heapq2
3
4def dijkstra(graph, start):5 dist = {node: float("inf") for node in graph}6 dist[start] = 07 pq = [(0, start)]8 while pq:9 d, node = heapq.heappop(pq)10 if d > dist[node]:11 continue # stale entry, a shorter path was already found12 for neighbor, weight in graph[node]:13 new_dist = d + weight14 if new_dist < dist[neighbor]:15 dist[neighbor] = new_dist16 heapq.heappush(pq, (new_dist, neighbor))17 return dist18
19
20graph = {21 "A": [("B", 4), ("C", 1)],22 "B": [("D", 1)],23 "C": [("B", 2), ("D", 5)],24 "D": [("E", 3)],25 "E": [],26}27
28for node, d in dijkstra(graph, "A").items():29 print(f"A -> {node}: {d}")Code Dijkstra's Algorithm bằng JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { C: 5, D: 10 },4 C: { E: 3 },5 D: { F: 11 },6 E: { D: 4 },7 F: {},8};9
10function dijkstra(source) {11 const dist = {};12 const visited = new Set();13 for (const node in graph) dist[node] = Infinity;14 dist[source] = 0;15 while (visited.size < Object.keys(graph).length) {16 // JS has no built-in heap: linear scan for the closest node (O(V^2))17 let u = null;18 for (const node in dist) {19 if (!visited.has(node) && (u === null || dist[node] < dist[u])) {20 u = node;21 }22 }23 if (dist[u] === Infinity) break;24 visited.add(u);25 for (const [v, w] of Object.entries(graph[u])) {26 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;27 }28 }29 return dist;30}31
32console.log("Shortest distances from A:", dijkstra("A"));Code Dijkstra's Algorithm bằng Java
1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4import java.util.PriorityQueue;5
6public class Main {7 public static void main(String[] args) {8 int n = 6;9 List<List<int[]>> adj = new ArrayList<>();10 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());11 int[][] edges = {12 {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5},13 {2, 3, 8}, {3, 4, 3}, {2, 5, 10}, {4, 5, 2}14 };15 for (int[] e : edges) {16 adj.get(e[0]).add(new int[]{e[1], e[2]});17 adj.get(e[1]).add(new int[]{e[0], e[2]});18 }19
20 int[] dist = new int[n];21 Arrays.fill(dist, Integer.MAX_VALUE);22 dist[0] = 0;23 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);24 pq.add(new int[]{0, 0}); // {node, distance}25 while (!pq.isEmpty()) {26 int[] cur = pq.poll();27 int node = cur[0], d = cur[1];28 if (d > dist[node]) continue; // stale queue entry29 for (int[] edge : adj.get(node)) {30 int next = edge[0], nd = d + edge[1];31 if (nd < dist[next]) {32 dist[next] = nd;33 pq.add(new int[]{next, nd});34 }35 }36 }37 System.out.println("Shortest distances from 0: " + Arrays.toString(dist));38 }39}Code Dijkstra's Algorithm bằng C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 const int INF = 1000000000;7 // Weighted directed graph: adj[u] = {(neighbor, weight), ...}8 std::vector<std::vector<std::pair<int, int>>> adj = {9 {{1, 4}, {2, 1}}, // 010 {{3, 1}}, // 111 {{1, 2}, {3, 5}}, // 212 {{4, 3}}, // 313 {}, // 414 };15 int n = static_cast<int>(adj.size());16 std::vector<int> dist(n, INF);17 dist[0] = 0;18 using State = std::pair<int, int>; // (distance, node)19 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;20 pq.push({0, 0});21 while (!pq.empty()) {22 auto [d, u] = pq.top();23 pq.pop();24 if (d > dist[u]) continue; // stale queue entry25 for (auto [v, w] : adj[u]) {26 if (d + w < dist[v]) {27 dist[v] = d + w;28 pq.push({dist[v], v});29 }30 }31 }32 for (int v = 0; v < n; ++v) {33 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";34 }35 return 0;36}Code Dijkstra's Algorithm bằng C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Weighted directed graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 4, 1, 0, 0},11 {0, 0, 0, 1, 0},12 {0, 2, 0, 5, 0},13 {0, 0, 0, 0, 3},14 {0, 0, 0, 0, 0},15 };16 int dist[N];17 bool done[N] = {false};18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // O(V^2) scan for the closest unfinished node (no heap needed here)21 for (int iter = 0; iter < N; iter++) {22 int u = -1;23 for (int v = 0; v < N; v++) {24 if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;25 }26 if (dist[u] == INF) break; // remaining nodes are unreachable27 done[u] = true;28 for (int v = 0; v < N; v++) {29 if (w[u][v] > 0 && dist[u] + w[u][v] < dist[v]) {30 dist[v] = dist[u] + w[u][v];31 }32 }33 }34 for (int v = 0; v < N; v++) {35 printf("Distance 0 -> %d: %d\n", v, dist[v]);36 }37 return 0;38}Câu hỏi thường gặp về thuật toán Dijkstra
Độ phức tạp thời gian của thuật toán Dijkstra là bao nhiêu?
O((V + E) log V). Phiên bản đơn giản duyệt mảng để tìm giá trị nhỏ nhất ở mỗi bước là O(V²), và thực tế có thể nhanh hơn trên đồ thị dày. Cả hai đều dùng O(V) bộ nhớ.Vì sao Dijkstra không chạy đúng với trọng số cạnh âm?
Dijkstra giả định rằng khi đã chốt đỉnh chưa chốt gần nhất, khoảng cách đó là cuối cùng. Một cạnh âm về sau có thể tạo ra đường đi ngắn hơn đến một đỉnh đã chốt, phá vỡ giả định này. Với đồ thị có trọng số âm, hãy dùng thuật toán Bellman-Ford.
Dijkstra và BFS khác nhau như thế nào?
BFS tìm đường đi ngắn nhất theo số cạnh (mỗi cạnh coi như có trọng số 1), dùng một hàng đợi thông thường. Dijkstra tổng quát hóa điều này cho đồ thị có trọng số bằng cách luôn mở rộng đỉnh có tổng khoảng cách nhỏ nhất, dùng hàng đợi ưu tiên. Trên đồ thị không trọng số, hai thuật toán cho ra cùng các đường đi.
Dijkstra và tìm kiếm A* khác nhau như thế nào?
A* là Dijkstra cộng thêm một heuristic ước lượng khoảng cách còn lại đến đích, nhờ vậy hướng việc tìm kiếm về phía mục tiêu thay vì lan đều ra mọi hướng. Khi heuristic bằng 0, A* trở thành chính Dijkstra. Dùng A* khi bạn có một đích duy nhất và một heuristic chấp nhận được tốt; dùng Dijkstra khi bạn cần khoảng cách đến mọi đỉnh.
Khi nào nên dùng Dijkstra thay cho Bellman-Ford?
O((V + E) log V) so với O(V·E) của Bellman-Ford. Chỉ chọn Bellman-Ford khi cạnh có thể âm hoặc bạn cần phát hiện chu trình âm. Trên đồ thị không âm, Dijkstra gần như luôn là lựa chọn tốt hơn.Dijkstra có thăm lại một đỉnh sau khi đã chốt không?
Không. Khi một đỉnh đã được chốt, khoảng cách của nó là cuối cùng và không bao giờ được nới lỏng lại. Một lỗi hay gặp khi cài đặt bằng heap là để lại các mục cũ trong hàng đợi ưu tiên sau khi khoảng cách của một đỉnh được cải thiện; bạn phải bỏ qua đỉnh vừa lấy ra nếu nó đã được chốt (khoảng cách lúc lấy ra lớn hơn khoảng cách đã ghi nhận). Quên bước kiểm tra này vẫn cho kết quả đúng nhưng tốn công vô ích.
Tài nguyên liên quan
Thêm mô phỏng trực quan
