Artikel ini perlu diterjemahkan dari bahasa Inggris ke bahasa Indonesia. Artikel ini ditulis atau diterjemahkan secara buruk dari Wikipedia bahasa Inggris. Jika halaman ini ditujukan untuk komunitas bahasa Inggris, halaman itu harus dikontribusikan ke Wikipedia bahasa Inggris. Lihat daftar bahasa Wikipedia. Artikel yang sama sekali tidak diterjemahkan dapat dihapus secara cepat sesuai kriteria A2. Jika Anda ingin memeriksa artikel ini, Anda boleh menggunakan mesin penerjemah. Namun ingat, mohon tidak menyalin hasil terjemahan tersebut ke artikel, karena umumnya merupakan terjemahan berkualitas rendah. |

Algoritma Dijkstra adalah algoritma untuk mencari lintasan terpendek dari satu simpul sumber ke simpul-simpul lain dalam graf berbobot yang bobot setiap sisinya tidak negatif. Dalam konteks ini, simpul dapat mewakili objek seperti kota, sedangkan sisi mewakili hubungan seperti jalan; bobot sisi dapat menyatakan jarak atau biaya. Algoritma ini berulang kali memilih simpul yang belum diproses dengan jarak sementara terkecil, lalu memperbarui jarak ke tetangga-tetangganya. Karena memilih pilihan terbaik pada setiap langkah, algoritma ini termasuk algoritma greedy. Jika jarak ke satu simpul tujuan saja yang diperlukan, proses dapat dihentikan setelah jarak terpendek ke simpul tersebut dipastikan.
Kode semu
1 fungsi Dijkstra(Graf, asal): 2 Q adalah himpunan titik 3 4 untuk setiap titik v dalam Graf: 5 jarak[v] ← tak hingga 6 sebelum[v] ← kosong 7 tambahkan v ke dalam Q 8 jarak[asal] ← 0; 9 10 selama Q tidak kosong: 11 u ← titik dalam Q dengan nilai jarak[u] terkecil 12 hapus u dari Q 13 14 untuk setiap tetangga v dari u: // hanya v yang masih dalam Q 15 alt ← jarak[u] + jarak_antara(u, v) 16 jika alt < jarak[v]: 17 jarak[v] ← alt 18 sebelum[v] ← u 19 20 kembalikan jarak[], sebelum[]
Rujukan
- E. W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269–271
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.3: Dijkstra's algorithm, pp. 595–601.
Lihat pula
Pranala luar
- Teori Jalan Terpendek Dijkstra oleh Jeremy Siek, dari Universitas Indiana
- Animasi algoritma Dijkstra
- Pustaka Boost Graph (BGL)
- Algoritma Dijkstra dalam JavaScript Diarsipkan 2006-07-02 di Wayback Machine
- Implementasi interaktif algoritma Dijkstra
- Masalah lintasan terpendek: algoritma Dijkstra Diarsipkan 2007-09-27 di Wayback Machine
- Applet algoritma Dijkstra