Algoritma Bellman–Ford: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
kTidak ada ringkasan suntingan |
Wadaihangit (bicara | kontrib) k Menambahkan foto ke halaman #WPWP |
||
| (16 revisi perantara oleh 13 pengguna tidak ditampilkan) | |||
Baris 1:
{{rapikan}}
[[Berkas:Bellman–Ford algorithm example.gif|jmpl|Contoh algoritma Bellman – Ford yang digunakan pada graf 5 titik]]
'''Algoritme Bellman–Ford''' menghitung jarak terpendek (dari satu sumber) pada sebuah digraf berbobot.
Maksudnya dari satu sumber ialah bahwa ia menghitung semua jarak terpendek yang berawal dari satu titik node.
▲Maksudnya dari satu sumber ialah bahwa ia menghitung semua jarak terpendek yang berawal dari satu titik node. Algoritma Dijkstra dapat lebih cepat mencari hal yang sama dengan syarat tidak ada sisi (edge) yang berbobot negatif. Maka Algoritma Bellman-Ford hanya digunakan jika ada sisi berbobot negatif.
Dalam konteks ini, [[bobot ekivalen]] dengan jarak dalam sebuah sisi.▼
▲Dalam konteks ini, bobot ekivalen dengan jarak dalam sebuah sisi.
''// Definisi tipe data dalam graf''
Baris 22:
'''function''' BellmanFord(''list'' semuatitik, ''list'' semuasisi, ''titik'' dari)
''// Argumennya ialah graf, dengan bentuk daftar titik ''
''// and sisi.
''// semuatitik sehingga atribut ''jarak'' dan ''sebelum'' ''
''// menyimpan jarak terpendek.''
Baris 29:
'''for each''' titik v in semuatitik:
'''if''' v '''is''' dari '''then''' v.jarak = 0
'''else''' v.jarak
v.sebelum
''// Perulangan relaksasi sisi''
'''for''' i '''from''' 1 '''to''' size(semuatitik):
'''for each''' sisi uv in semuasisi:
u
v
'''if''' v.jarak > u.jarak + uv.bobot
v.jarak
v.sebelum
''// Cari sirkuit berbobot(jarak) negatif''
'''for each''' sisi uv in semuasisi:
u
v
'''if''' v.jarak > u.jarak + uv.bobot
'''error''' "Graph mengandung siklus berbobot total negatif"
Secara umum ''coding'' algoritme dapat juga menggunakan [[teknik]] ''coding'' pemrograman yang lain.
{{komputer-stub}}
[[Kategori:
| |||