Algoritma Dijkstra: Perbedaan antara revisi

Konten dihapus Konten ditambahkan

Sebaris

Revisi terkini sejak 11 Januari 2022 04.46

Algoritme 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 bernilai nonnegatif, $[0,\infty )$ . Input algoritme ini adalah sebuah graf berarah yang berbobot (weighted directed graph) $G$ dan sebuah titik asal $s$ dalam himpunan garis $V$ .

Misalnya, bila titik dari sebuah graf melambangkan kota-kota dan bobot garis melambangkan jarak antara kota-kota tersebut, algoritme Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.

Biaya (cost) dari sebuah garis dapat dianggap sebagai jarak antara dua simpul, yaitu jumlah jarak semua garis dalam jalur tersebut. Untuk sepasang titik $s$ dan $t$ dalam $V$ , algoritme ini menghitung jarak terpendek dari $s$ ke $t$ .

Kode semu[sunting | sunting sumber]

 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[sunting | sunting sumber]

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[sunting | sunting sumber]

Pranala luar[sunting | sunting sumber]

@@ Baris 1: / Baris 1: @@
 {{terjemah|Inggris}}
+[[Berkas:Dijkstra_Animation.gif|jmpl|Algoritme Dijkstra]]
-'''Algoritma Dijkstra''', dinamai menurut penemunya, [[Edsger Dijkstra]], adalah sebuah algoritma rakus (''greedy algorithm'') dalam memecahkan permasalahan jarak terpendek (''shortest path problem'') untuk sebuah graf berarah (''directed graph'') dengan bobot-bobot sisi (''edge weights'') yang bernilai tak-negatif.
+'''Algoritme 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 bernilai nonnegatif, ''<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]]'' dari sebuah graf melambangkan kota-kota dan bobot sisi (''edge weights'') melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.
+Misalnya, bila titik dari sebuah graf melambangkan kota-kota dan bobot garis melambangkan jarak antara kota-kota tersebut, algoritme Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.
+Biaya (''cost'') dari sebuah garis dapat dianggap sebagai jarak antara dua simpul, yaitu jumlah jarak semua garis dalam jalur tersebut. Untuk sepasang titik ''<math>s</math>'' dan ''<math>t</math>'' dalam ''<math>V</math>'', algoritme ini menghitung jarak terpendek dari ''<math>s</math>'' ke ''<math>t</math>''.
-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''.
+== Kode semu ==
-Setiap sisi dari graf ini adalah pasangan vertices (''u'',''v'') yang melambangkan hubungan dari ''vertex'' ''u'' ke ''vertex'' ''v''. Himpunan semua tepi disebut ''E''.
+'''fungsi''' Dijkstra(''Graf'', ''asal''):
+''Q'' adalah himpunan titik
-Bobot (''weights'') dari semua sisi dihitung dengan fungsi
- ''w'': ''E'' → [0, ∞)
+'''untuk setiap''' titik ''v'' dalam ''Graf'':
-jadi ''w''(''u'',''v'') adalah jarak tak-negatif dari vertex ''u'' ke vertex ''v''.
+jarak[''v''] ← tak hingga
+sebelum[''v''] ← kosong
-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''.
+tambahkan ''v'' ke dalam ''Q''
+jarak[''asal''] ← 0;
-== Pseudocode ==
-'''function''' Dijkstra(G, w, s)
+'''selama''' ''Q'' '''tidak''' kosong:
-'''for each''' vertex v in V[G]                        ''// Initializations''
-d[v] := infinity
+''u'' ← titik dalam ''Q'' dengan nilai jarak[''u''] terkecil
-previous[v] := undefined
+hapus ''u'' dari ''Q''
-d[s] := 0                                        ''// Distance from s to s''
+'''untuk setiap''' tetangga ''v'' dari ''u'': // hanya ''v'' yang masih dalam ''Q''
-S := empty set
+''alt'' ← jarak[''u''] + jarak_antara(''u'', ''v'')
-Q := V[G]                                        ''// Set of all vertices''
+'''jika''' ''alt'' < jarak[''v'']:
-'''while''' Q is not an empty set                      ''// The algorithm itself''
-u := Extract_Min(Q)
+jarak[''v''] ← ''alt''
-S := S union {u}
+sebelum[''v''] ← ''u''
-'''for each''' edge (u,v) outgoing from u
+'''kembalikan''' jarak[], sebelum[]
-'''if''' d[u] + w(u,v) < d[v]             ''// Relax (u,v)''
-d[v] := d[u] + w(u,v)
-previous[v] := u
 == Rujukan ==
@@ Baris 43: / Baris 42: @@
 * [http://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html Animation of Dijkstra's algorithm]
 * [http://www.boost.org/libs/graph/doc/index.html The Boost Graph Library (BGL)]
-* [http://www.itonsite.co.uk/allanboydproject/section4_2.htm Javascript Dijkstra's Algorithm]
+* [http://www.itonsite.co.uk/allanboydproject/section4_2.htm JavaScript 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://students.ceid.upatras.gr/~papagel/english/java_docs/minDijk.htm Interactive Implementation of Dijkstra's Algorithm]
-* [http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml Shortest Path Problem: Dijkstra's Algorithm]
+* [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 }}
 * [http://www.unf.edu/~wkloster/foundations/DijkstraApplet/DijkstraApplet.htm Dijkstra's Algorithm Applet]
-[[Kategori:Algoritma|Dijkstra]]
+[[Kategori:Algoritme|Dijkstra]]
-[[bg:Алгоритъм на Дейкстра]]
-[[cs:Dijkstrův algoritmus]]
-[[de:Dijkstra-Algorithmus]]
-[[en:Dijkstra's algorithm]]
-[[es:Algoritmo de Dijkstra]]
-[[fa:الگوریتم دیکسترا]]
-[[fi:Dijkstran algoritmi]]
-[[fr:Algorithme de Dijkstra]]
-[[he:אלגוריתם דייקסטרה]]
-[[hr:Dijkstrin algoritam]]
-[[hu:Dijkstra-algoritmus]]
-[[it:Algoritmo di Dijkstra]]
-[[ja:ダイクストラ法]]
-[[ko:데이크스트라 알고리즘]]
-[[lt:Dijkstros algoritmas]]
-[[nl:Kortstepad-algoritme]]
-[[no:Dijkstras algoritme]]
-[[pl:Algorytm Dijkstry]]
-[[pt:Algoritmo de Dijkstra]]
-[[ro:Algoritmul lui Dijkstra]]
-[[ru:Алгоритм Дейкстры]]
-[[sk:Dijkstrov algoritmus]]
-[[sl:Dijkstrov algoritem]]
-[[sr:Дајкстрин алгоритам]]
-[[sv:Dijkstras algoritm]]
-[[uk:Алгоритм Дейкстри]]
-[[vi:Thuật toán Dijkstra]]
-[[zh:迪科斯彻算法]]