Algoritma Johnson 4


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

Titik awal Titik Tujuan Jarak
Titik A Titik B 6
Titik A Titik E 7
Titik B Titik C 5
Titik B Titik D -4
Titik B Titik E 8
Titik C Titik B -2
Titik D Titik C 7
Titik E Titik C -3
Titik E Titik D 9

Contoh data awal adalah sebagai berikut:

Jika diilustrasikan dalam gambar, maka model data awal adalah sebagai berikut
bellman ford awal


Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan proses pencarian jalur dengan metode Bellman-Ford
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1a – 1e)

Memasuki perhitungan pada fungsi BellmanFord

1a. Lakukan inisialisasi variabel titik tujuan sebanyak jumlah titik
variabel ini digunakan untuk menyimpan titik tujuan pada masing-masing indeks titik
Beri nilai awal pada pasing-masing titik tujuan dengan angka -1

1b. Beri nilai awal jarak pada titik awal dengan 0

1c. Lakukan perulangan pada semua titik awal secara terurut
Untuk masing-masing titik awal, lakukan perulangan pada semua titik tujuan yang ditemukan (poin 1c1 – 1c2)

1c1. jika jarak dari titik tujuan lebih dari jarak titik awal ditambah bobotnya,
maka pilih titik awal ini sebagai titik tujuan

1c2. lakukan perulangan terhadap semua titik tetangga dari titik tujuan (poin 1c2a)

1c2a. jika jarak dari titik tetangga lebih dari jarak titik tujuan ditambah bobotnya,
maka pilih titik tetangga ini sebagai titik tujuan

1d. Lakukan perulangan pada semua titik awal dan titik tujuan
jika jarak dari titik tujuan lebih dari jarak titik awal ditambah bobotnya,
maka hentikan perhitungan dan kembalikan nilai fungsi ini dengan nilai false

1e. Jika kondisi nomor 4 tidak terpenuhi, maka kembalikan nilai fungsi ini dengan nilai true

2. Catat hasil sementara untuk masing-masing jawaban jarak yang ditemukan
Kemudian hitung total jarak dengan menjumlahkan semua jarak yang ditemukan

3. Lakukan pembobotan ulang pada masing-masing bobot yang ada untuk menghilangkan bobot dengan nilai negatif
Nilai bobot yang baru dihitung dengan rumus
garis[u][v] = garis[u][v] + jarak[u] – jarak[v]

4. Setelah tidak ada bobot dengan nilai negatif,
maka lakukan pencarian jalur terpendek dari masing-masing titik menggunakan metode Dijkstra
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 4a – 4d)

Memasuki perhitungan pada fungsi Dijkstra

4a. Inisialisasi Array Jarak ke titik lain
Pada array tersebut, selain indeks titik awal, beri nilai jarak dengan angka yang sangat besar

4b. Inisialisasi Array Titik Terpilih menjadi benar semua, artinya semua titik tersedia untuk dihitung
Kemudian beri nilai array Jalur Sebelumnya menjadi -1

4c. Lakukan perhitungan selama masih ada titik yang belum dihitung (poin 4c1 – 4c7)

4c1. Beri nilai awal jarak dengan nilai yang sangat besar

4c2. Untuk masing-masing titik yang sudah terpilih,
Hitung jarak terpendek ke titik lain, dan simpan indeks titik dengan jarak terpendek

4c3. Jika nilai jarak tidak ditemukan, maka perhitungan selesai karena tidak ada titik lain yang menghasilkan jarak lebih pendek

4c4. Beri nilai false untuk titik terpilih agar tidak dihitung pada perulangan berikutnya

4c5. Cari semua titik tujuan dari indeks titik yang terpilih (indeks u)
Lakukan perhitungan berikutnya apabila titik tujuan tersebut sudah terpilih dan terdapat jarak yang sah antara titik u dan titik tujuan

4c6. Hitung jarak alternatif dari titik terpilih

4c7. Jika jarak yang melalui titik tujuan kurang dari nilai akumulasi jarak pada titik tersebut,
maka simpan data jarak yang baru
dan simpan indeks titik terpilih (titik u) sebagai data jalur sebelumnya dari titik tujuan

4d. Setelah perhitungan pada poin diatas selesai,
maka untuk masing-masing titik,
lakukan pencatan jalur dimulai dari titik tersebut dan hitung jumlah titik yang dilewati jalur tersebut
Ambil jalur dengan jumlah titik paling banyak dan bobot yang paling rendah

5. Setelah menemukan jalur terbaik, maka kembalikan nilai bobot seperti semua
Untuk mengembalikan nilai bobot seperti semula dapat menggunakan rumus
garis[u][v] = garis[u][v] + jarak[v] – jarak[u]

6. Hitung total bobot dengan menjumlahkan semua bobot pada jalur yang ditemukan

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Titik untuk menampung semua data titik beserta jalurnya. Deklarasi Class Titik adalah sebagai berikut:


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd83

Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut
bellman ford akhir


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.


Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

4 pemikiran di “Algoritma Johnson

  • Ilham saputra

    Saya tertarik mempelajari algoritma johnson ini min, setelah saya baca ada pertanyaan ni min
    Dari penjelasan diatas kan algoritma johnson menggabungkan bellman-ford dan dijkstra, dimana bellman-ford digunakan untuk menghilangkan nilai negatif pada jarak antar titik dan dijkstra untuk mencari jalur terpendeknya
    Nah bagaimana jika dalam contoh kasusnya tidak ada nilai negatif pada jarak antar titik, apakah langsung dilakukan perhitungan mencari jarak terpendek dengan algoritma dijkstra? Terimakasih min ditunggu kali jawabannya ??

    • pip Penulis

      Menurut pemahaman yang saya ketahui mengenai algoritma ini, kesimpulan saya sama dengan kesimpulan anda, yaitu perhitungan langsung dilakukan dengan Algoritma Dijkstra. Untuk dapat tetap menggunakan algoritma ini, perlu diingat bahwa nilai diantara 2 titik tidak selalu diukur menggunakan nliai yang pasti bernilai positif (misalnya jarak), tetapi bisa juga diukur menggunakan nilai yang tidak selalu positif (misalnya biaya, poin, dan lain-lain)

        • pip Penulis

          Menurut saya sudah tidak bisa dikatakan seperti itu karena kedua hal ini adalah algoritma yang berbeda. Silahkan menggunakan Algoritma Dijkstra apabila tujuan anda memang menggunakan algoritma tersebut.