Dalam dunia optimasi dan analisis jaringan, menemukan jalur terpendek antara dua simpul dalam sebuah graf adalah masalah fundamental. Berbagai algoritma telah dikembangkan untuk tujuan ini, seperti Dijkstra untuk graf dengan bobot non-negatif, dan Bellman-Ford yang mampu menangani bobot negatif namun memiliki kompleksitas waktu yang lebih tinggi. Namun, ketika dihadapkan pada graf berbobot negatif yang tidak memiliki siklus negatif, algoritma Johnson menawarkan solusi yang efisien dan elegan.
Graf berbobot negatif seringkali muncul dalam berbagai skenario, misalnya dalam pemodelan biaya, penalti, atau penundaan yang bisa saja bernilai negatif. Keberadaan bobot negatif ini menghalangi penggunaan algoritma seperti Dijkstra karena asumsi bahwa bobot tepi selalu positif yang menjadi dasar cara kerjanya. Siklus negatif (jalur yang dimulai dan berakhir di simpul yang sama dengan total bobot negatif) adalah masalah yang lebih serius, karena jalur terpendek bisa menjadi tidak terdefinisi (mendekati tak terhingga negatif).
Ilustrasi graf berbobot (negatif dan positif).
Inti dari algoritma Johnson adalah mengubah bobot tepi pada graf asli menjadi bobot non-negatif sedemikian rupa sehingga jalur terpendek di graf asli tetap sama dengan jalur terpendek di graf yang telah diubah bobotnya. Ini dicapai melalui langkah-langkah berikut:
s, ditambahkan ke graf asli. Simpul ini terhubung ke semua simpul lain dalam graf dengan tepi yang memiliki bobot nol.
s ke semua simpul lainnya. Langkah ini krusial karena Bellman-Ford dapat mendeteksi siklus negatif. Jika Bellman-Ford mendeteksi siklus negatif, maka algoritma Johnson akan berhenti dan melaporkan bahwa tidak ada jalur terpendek yang terdefinisi.
h(v) untuk setiap simpul v dihitung berdasarkan jarak terpendek dari simpul sumber baru s ke simpul v yang diperoleh dari langkah Bellman-Ford. Nilai h(v) ini sering disebut sebagai "potensial" simpul.
(u, v) pada graf asli diubah menggunakan rumus: w'(u, v) = w(u, v) + h(u) - h(v). Dengan menggunakan identitas ini, terbukti bahwa semua tepi baru w'(u, v) akan memiliki bobot non-negatif. Pembuktian matematisnya didasarkan pada ketidaksamaan segitiga yang berlaku pada hasil Bellman-Ford.
jarak_asli(u, v) = jarak_dijkstra(u, v) - h(u) + h(v).
Algoritma Johnson menggabungkan kekuatan Bellman-Ford dan Dijkstra. Kompleksitas waktu algoritma ini ditentukan oleh langkah-langkahnya:
Secara keseluruhan, kompleksitas waktu dominan adalah O(V * E + V * (E + V log V)), yang sering disederhanakan menjadi O(V * E log V) atau O(V^2 log V + V*E) untuk graf jarang dan O(V^3) untuk graf padat.
Algoritma Johnson adalah solusi yang sangat baik untuk menemukan semua pasangan jalur terpendek dalam graf berbobot negatif tanpa siklus negatif. Keunggulannya meliputi:
Gunakan algoritma Johnson ketika Anda memerlukan semua pasangan jalur terpendek dan graf Anda diketahui memiliki bobot negatif, tetapi dipastikan tidak ada siklus negatif. Jika graf hanya memiliki bobot non-negatif, Dijkstra yang dijalankan dari setiap simpul akan lebih efisien.
Dalam praktiknya, pemahaman dan penerapan algoritma Johnson memungkinkan penyelesaian masalah optimasi yang lebih kompleks dalam berbagai bidang, mulai dari logistik, perencanaan jaringan, hingga analisis jalur dalam sistem yang dinamis.