Thuật toán Johnson

Thuật toán Johnson

Phân loại	Bài toán về đường đi ngắn nhất cho tất cả các cặp (đối với đồ thị có trọng số)
Cấu trúc dữ liệu	Đồ thị
Hiệu suất trường hợp tệ nhất	${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$

Thuật toán Johnson được Donald B. Johnson tìm ra năm 1977^[1]. Thuật toán Johnson là một thuật toán giải quyết bài toán đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có hướng, có trọng số và không có chu trình âm. Nó hoạt động bằng cách sử dụng thuật toán Bellman – Ford để tính toán một phép biến đổi của đồ thị đầu vào loại bỏ tất cả các trọng số âm, cho phép thuật toán Dijkstra được sử dụng trên đồ thị đã biến đổi^[2][3].

Bài toán

Nếu đã tìm hiểu về Thuật toán Dijkstra và Thuật toán Floyd-Warshall thì chúng ta biết rằng với đồ thị không có trọng số âm thì thuật toàn Dijkstra sẽ có tốc độ xử lý nhanh nhất ${\displaystyle O(n^{2}+m)}$

còn Floyd-Warshal thì tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong thời gian ${\displaystyle O(n^{3})}$. Mở rộng hơn nếu chúng ta áp dụng thuật toán Dijkstra (với Fibonacci Heap) ${\displaystyle n}$ lần, ta sẽ thu được thuật toán nhanh hơn hẳn ${\displaystyle O(m+n\log n)}$

Vấn đề đặt ra là có tồn tại hay không thuật toán ${\displaystyle O(m+n\log n)}$ tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có hướng, có trọng số âm và không có chu trình âm?

Thuật toán Johnson được tạo ra để giải quyết vấn đề này.

Giới thiệu thuật toán

Ý tưởng của thuật toán là từ đồ thị đã cho, tìm cách chuyển nó thành đồ thị có trọng số không âm rồi dùng thuật toán Dijkstra áp dụng cho từng đỉnh

Mô tả thuật toán

Thuật toán Johnson có 4 bước cơ bản:

1. Thêm vào ${\displaystyle G}$ một đỉnh ${\displaystyle s}$ và với mỗi ${\displaystyle x\in V}$, thêm cung ${\displaystyle (s\rightarrow v)}$ có trọng số ${\displaystyle w(s\rightarrow v)=0}$
2. Áp dụng thuật toán Bellman-Ford tìm khoảng cách ngắn nhất ${\displaystyle \delta (s,x)}$ từ ${\displaystyle s}$ tới mọi ${\displaystyle x\in V}$ và sử dụng khoảng cách đó làm thế năng của đỉnh ${\displaystyle x}$, i.e, ${\displaystyle p(x)=\delta (s,x)}$
3. Gán cho mỗi cung ${\displaystyle (u\rightarrow v)\in {\overrightarrow {E}}}$một trọng số mới.${\displaystyle \vartriangle (u\rightarrow v)=w(u\rightarrow v)+p(u)-p(v)}$. Gọi đồ thị với trọng số mới là ${\displaystyle H}$ (${\displaystyle H}$ là đồ thì có trọng số không âm)
4. Áp dụng Dijkstra ${\displaystyle V}$ lần cho đồ thị ${\displaystyle H}$để tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong${\displaystyle H}$. Gọi ${\displaystyle \delta _{H}(x,y),\delta (x,y)}$ lần lượt là khoảng cách từ ${\displaystyle x}$ tơi ${\displaystyle y}$ trong ${\displaystyle H}$ và ${\displaystyle G}$. độ lệch của đường đi ngắn nhất từ ${\displaystyle x}$ tới ${\displaystyle y}$ chính là ${\textstyle \delta (x,y)=\delta _{H}(x,y)+p(y)-p(x)}$ Từ đó suy ra: ${\textstyle \delta (x,y)=\delta _{H}(x,y)+p(y)-p(x)}$.

Mô tả theo cách nông dân thì:

1. Thêm một đỉnh ${\displaystyle s}$ vào đồ thị ${\displaystyle G}$, có cạnh đến bất kỳ đỉnh nào của ${\displaystyle G}$ cũng được và ${\displaystyle s}$ có trọng số là 0.(ở hình bên dưới là đỉnh q)
2. Dùng thuật toán Bellman-Ford, tìm đường đi từ ${\displaystyle s}$ đến các đỉnh còn lại. (kết quả được đồ thị thứ 2 ở hình bên dưới)
3. Thay đổi trọng số của đồ thị đã cho ${\displaystyle G}$ bằng đồ thị mới ${\displaystyle H}$ có trọng số không âm bằng cách, Mỗi cạnh từ u đến v có trọng số ${\displaystyle w(u\rightarrow v)}$ thay bằng giá trị mới ${\displaystyle \vartriangle (u\rightarrow v)=w(u\rightarrow v)+p(u)-p(v)}$.(kết quả được đồ thị thứ 3 ở hình bên dưới)
4. Dùng thuật toán Dijsktra với đồ thị ${\displaystyle H}$

Chú thích

1. Johnson, Donald B. (1977), “Efficient algorithms for shortest paths in sparse networks”, Journal of the ACM, 24 (1): 1–13, doi:10.1145/321992.321993.
2. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms, MIT Press and McGraw-Hill, ISBN 978-0-262-03293-3. Section 25.3, "Johnson's algorithm for sparse graphs", pp. 636–640.
3. Black, Paul E. (2004), “Johnson's Algorithm”, Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology.