Lượt xem | |
Hiện tại: | |
1h trước: | |
24h trước: | |
Tổng số: |
I. Phát biểu bài toán:
Có rất nhiều giải thuật đã được phát triển để giải bài toán tìm đường đi ngắn nhất giữa một cặp đỉnh, trong khuôn khổ bài viết này chúng tôi chỉ xin giới thiệu giải thuật Dijkstra. Giải thuật Dijkstra là một giải thuật để giải bài toán đường đi ngắn nhất nguồn đơn trên một đồ thị có trọng số cạnh mà tất cả các trọng số đều không âm.
Tìm đường đi ngắn nhất từ một đỉnh đến một đỉnh khác trong đồ thị liên thông có trọng số dương bằng thuật toán Dijkstra.
Ý tưởng:
Lưu trữ độ dài đường đi từ a đến v ở lần lặp thứ i
Những đỉnh thuộc S sẽ có nhãn cố định
Lk(v) = min { Lk-1(v); Lk-1(u) + w(uv) }
II. Thuật toán
Xác định đường đi ngắn nhất giữa hai đỉnh cho trước, từ đỉnh a đến đỉnh b.
Ở mỗi đỉnh v, giải thuật Dijkstra xác định 3 thông tin: kv, dv và pv.
kv = false, “ v Î V.
Khởi tạo, dv = ¥,“v Î V {a}, da = 0.
Các bước của giải thuật Dijkstra:
B1. Khởi tạo: Đặt kv:= false “v Î V; dv:= ¥,“v Î V {a}, da:=0.
B2. Chọn v Î V sao cho kv = false và dv = min {dt / tÎ V, kt = false}
Nếu dv = ¥ thì kết thúc, không tồn tại đường đi từ a đến b.
B3. Đánh dấu đỉnh v, kv:= true.
B4. Nếu v = b thì kết thúc và dblà độ dài đường đi ngắn nhất từ a đến b.
Ngược lại nếu v ¹ b sang B5.
B5. Với mỗi đỉnh u kề với v mà ku = false, kiểm tra
Nếu du > dv + w(v,u) thì du:= dv + w(v,u)
Ghi nhớ đỉnh v: pu:= v.
Quay lại B2.
III. Độ phức tạp của thuật toán:
Gọi f(n) là số lần giải thuật Dijkstra khảo sát một cạnh của đồ thị G trong trường hợp xấu nhất. Khi đó ta có:
f(n) < O(|V|2)
Chứng minh: Cho n = |V|, B5 là vòng lặp chứa các bước B2 ® B5, vòng lặp được thực hiện đến khi v = b.Vì ở mỗi vòng lặp ta rút ra một đỉnh của V và khởi đầu V có n phần tử, nên vòng lặp được xử lý nhiều nhất là n lần.
Ở B2 số đỉnh tối đa được khảo sát là n – 1 đỉnh
Ở B5 số đỉnh kề tối đa được khảo sát là n -1 đỉnh
Do đó: f(n) £ 2(n-1)n < O(|V|2)
Vậy độ phức tạp của giải thuật Dijkstra là O(|V|2).
IV. Demo
Download demo & source code:
2015-01-08 07:00:11
Nguồn: https://nguyenhaiblog.wordpress.com/2014/01/15/thuat-toan-dijsktra/