Algoritma Dijkstra: Perbedaan antara revisi

'''AlgoritmaAlgoritme Dijkstra''', (dinamai menurut penemunya, seorang ilmuwan komputer, [[Edsger Dijkstra]]), adalah [[sebuah algoritme rakus (''greedy algorithm]]'') yang dipakai dalam memecahkan [[permasalahan jarak terpendek (''shortest path problem]]'') untuk sebuah [[graf]] berarah (''directed graph]]'') dengan bobot-bobot garis (''edge weights'') yang tidakbernilai negatifnonnegatif, ''<math>[0, \infty)</math>''. Input algoritme ini adalah sebuah graf berarah yang berbobot (''weighted directed graph'') <math>G</math> dan sebuah titik asal ''<math>s</math>'' dalam himpunan garis ''<math>V</math>''.

Misalnya, bila [[vertices]]titik dari sebuah graphgraf melambangkan kota-kota dan edgebobot weightsgaris melambangkan jarak antara kota-kota tersebut, algoritmaalgoritme Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.

Input algoritma ini adalah sebuah weighted directed graph ''G'' dan sebuah source vertex ''s'' dalam ''G''. ''V'' adalah himpunan semua [[vertexBiaya (graph theory)|vertices]] dalam graph ''Gcost''. Setiap [[edge (graph theory)|edge]] dari graph ini adalah pasangan vertices (''u'',''v'') yang melambangkan hubungan dari vertex ''u'' ke vertex ''v''. Himpunan semua edge disebut ''E''. Weights dari edges dihitung dengan fungsi ''w'': ''E'' → [0, ∞); jadi ''w''(''u'',''v'') adalah jarak non-negatif dari vertex ''u'' ke vertex ''v''. Cost dari sebuah edgegaris dapat dianggap sebagai jarak antara dua vertexsimpul, yaitu jumlah jarak semua edgegaris dalam pathjalur tersebut. Untuk sepasang vertextitik ''<math>s</math>'' dan ''<math>t</math>'' dalam ''<math>V</math>'', algoritmaalgoritme ini menghitung jarak terpendek dari ''<math>s</math>'' ke ''<math>t</math>''.

== PseudocodeKode semu ==

1 '''functionfungsi''' Dijkstra(G''Graf'', w, s''asal''):

4 '''untuk setiap''' titik ''v'' dalam previous[v] ''Graf'':= undefined

6 S := empty set sebelum[''v''] ← kosong

7 Q := V[G] tambahkan ''v'' ke dalam ''// Set of all verticesQ''

10 '''selama''' ''Q'' '''tidak''' S kosong:= S union {u}

11 ''u'for' ← titik dalam each''Q'' edgedengan (u,v) outgoing fromnilai jarak[''u''] terkecil

12 hapus '''if'u'' d[u] + w(u,v) < d[v] dari ''// Relax (u,v)Q''

14 '''untuk setiap''' tetangga ''v'' dari ''u'': // hanya ''v'' yang masih dalam previous[v] := u''Q''

* [[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&ndash;601595–601.

== Lihat jugapula ==

* [http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html Teori Jalan Terpendek Dijkstra oleh Jeremy Siek, dari Universitas Indiana]

* [http://www.itonsite.co.uk/allanboydproject/section4_2.htm JavascriptJavaScript Dijkstra's Algorithm] {{Webarchive|url=https://web.archive.org/web/20060702173918/http://www.itonsite.co.uk/allanboydproject/section4_2.htm |date=2006-07-02 }}

* [http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml Shortest Path Problem: Dijkstra's Algorithm] {{Webarchive|url=https://web.archive.org/web/20070927234553/http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml |date=2007-09-27 }}

[[Kategori:AlgoritmaAlgoritme|Dijkstra]]