Algoritma Dijkstra: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
kTidak ada ringkasan suntingan |
k Bot: Perubahan kosmetika |
||
Baris 8:
Input algoritma ini adalah sebuah graf berarah yang berbobot (''weighted directed graph'') ''G'' dan sebuah sumber ''[[vertex]]'' ''s'' dalam ''G'' dan ''V'' adalah himpunan semua [[vertices]] dalam graph ''G''.
Setiap sisi dari graf ini adalah pasangan vertices (''u'',''v'') yang melambangkan hubungan dari ''vertex'' ''u'' ke ''vertex'' ''v''. Himpunan semua tepi disebut ''E''.
Bobot (''weights'') dari semua sisi dihitung dengan fungsi
''w'': ''E'' → [0, ∞)
jadi ''w''(''u'',''v'') adalah jarak tak-negatif dari vertex ''u'' ke vertex ''v''.
Ongkos (''cost'') dari sebuah sisi dapat dianggap sebagai jarak antara dua ''vertex'', yaitu jumlah jarak semua sisi dalam jalur tersebut. Untuk sepasang vertex ''s'' dan ''t'' dalam ''V'', algoritma ini menghitung jarak terpendek dari ''s'' ke ''t''.
| |||