ban nào rành về thuật toán dijkstra có thế giúp mình 1 chút không .vì đọc code trên mạng thấy mông lung quá.mà k có giải thích rõ ràng nữa .xin cảm ơn!
Hỏi về thuật toán dijkstra
Chắc tại bạn chưa tìm đúng nguồn để đọc.
minh bi hạn chế về ngoại ngữ
bạn có thể ib riêng giúp mình k?
Hạn chế thì đọc và học dần là biết. Tiếng Anh là 1 điều bắt buộc đối với coder. Hơn nữa Geeksforgeeks giải thích rất dễ hiểu, tiếng Anh của họ không phải quá hàn lâm, học sinh cấp 2 vẫn có thể đọc được đến 80%, phần còn lại vừa đọc vừa đoán được.
Không. Mình lâu lắm rồi không học thuật toán này, mình cũng quên sạch sẽ rồi, và cũng vì lí do mình đã kể trên.
Tư tưởng chủ đạo: để tìm đường ngắn nhất từ A đến B thì phải tìm C sao cho đường ngắn nhất từ A đến C + cạnh CB là ngắn nhất. Lưu ý là nếu không thể tối ưu cục bộ thì không dùng được 
và nếu có trọng số âm thì sẽ mất tính đơn điệu và phải dùng thuật toán khác.
Đây là thuật toán cơ bản O(|V|) mem và O(|E| + |V|^2) time (chuối :D)
Khởi động: cho đồ thị G(V, E) tạo ra một mảng M[x] === min(A, x) với mọi x thuộc V. Gán min(A, A) := 0, còn lại là +inf.
Vòng lặp: Từ M[] chọn x sao cho M[x] min. Kí hiệu cạnh xy là cạnh hướng từ x ra y, từ x kiểm tra tất cả các cạnh kề xy và cập nhật M[y]:= min(min(xy < +inf)(M[x] + xy), M[y]).
Ví dụ: đồ thị có hướng, từ A đến B với V = {A, B, C, D, E, F} và E:
AB = 16, AC = 4, AD = 9
CB = 5, CD = 4, CE = 7
DB = 9, DE = 3, DF = 2
EB = 6, EF = 4, EA = 1
A: M[‘A’] = 0, M[‘B’] = 16, M[‘C’] = 4, M[‘D’] = 9
C: M[‘B’] = 4+5 = 9, M[‘D’] = 4+4 = 8 < 9, M[‘E’] = 4+7 = 11
D: M[‘B’] = 8+9 = 17 > 9 (bỏ), M[‘E’] = 8+3 = 11 >= 11 (bỏ), M[‘F’] = 8+2 = 10
B là đích, không xét (đi đâu nữa :D, nhưng chỉ riêng bài này thôi)
F: không có.
E: M[‘B’] = 10+6 = 16 > 9 (bỏ), M[‘F’] = 11+4 = 15 > 10 (bỏ), M[‘A’] = 11+1 = 12 > 0 (bỏ).
Để chọn đỉnh nhanh chóng thì phải có min-heap (gốc nhỏ hơn hai nhánh).
(phần dưới này có thể bỏ qua :D) Đọc câu đầu tiên, một số người sẽ nghĩ đến “tam giác” 1 - 2 - 4, nhưng nghĩ lại mà xem sao không đi qua cạnh 2, thì 1+2 = 3 rồi còn gì.
Với đồ thị vô hướng, số lần xét thực chất là 2|E|
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?