Thực đơn
Thuật_toán_Johnson Bài toánNế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 O ( n 2 + m ) {\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 O ( n 3 ) {\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) n {\displaystyle n} lần, ta sẽ thu được thuật toán nhanh hơn hẳn O ( m + n log n ) {\displaystyle O(m+n\log n)}
Vấn đề đặt ra là có tồn tại hay không thuật toán O ( m + n log 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.
Thực đơn
Thuật_toán_Johnson Bài toánLiên quan
Thuật ngữ giải phẫu cử động Thuật toán Thuật ngữ anime và manga Thuật ngữ thiên văn học Thuật ngữ lý thuyết đồ thị Thuật chiêu hồn Thuật toán Dijkstra Thuật ngữ tin học Thuật toán Kruskal Thuật ngữ ngữ âm họcTài liệu tham khảo
WikiPedia: Thuật_toán_Johnson //doi.org/10.1145%2F321992.321993 https://xlinux.nist.gov/dads/HTML/johnsonsAlgorith... https://en.wikipedia.org/wiki/File:Johnson's_algor...