Algoritma Johnson adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik dengan jarak terpendek.
Secara singkat, Algoritma ini adalah penggabungan dari Algoritma Bellman-Ford dan Algoritma Dijkstra yang sudah dijelaskan sebelumnya. Setelah mendapatkan nilai jarak yang baru dengan menggunakan Bellman-Ford, maka lakukan proses pembobotan ulang untuk menghilangkan nilai jarak negatif. Jika semua jarak sudah bernilai positif, maka pencarian jalur dapat dilakukan dengan metode Dijkstra. Setelah jalur ditemukan, kembalikan nilai bobot seperti semula untuk mencatat total bobot yang sebenarnya
Diasumsikan ada sebaran titik yang harus dilalui semuanya
semua titik tidak terhubung secara langsung dengan titik-titik lainnya, melainkan hanya melalui jalur tertentu saja setiap jalur juga memiliki bobot sendiri-sendiri
Tentukan Jalur yang harus diambil untuk mengelilingi semua titik dengan jarak terpendek
Diasumsikan data jalur yang tersedia adalah sebagai berikut
