Wikipedia

Algoritma Dijkstra: Perbedaan antara revisi

Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
Thijs!bot (bicara | kontrib)
71.934 suntingan
k robot Adding: sk:Dijkstrov algoritmus
k Hysocc memindahkan halaman Algoritme Dijkstra ke Algoritma Dijkstra dengan menimpa pengalihan lama
 
(41 revisi perantara oleh 29 pengguna tidak ditampilkan)
Baris 1:
{{terjemah|Inggris}}
[[Berkas:Dijkstra_Animation.gif|jmpl|Algoritme Dijkstra]]
 
'''AlgoritmaAlgoritme Dijkstra''', (dinamai menurut penemunya, seorang ilmuwan komputer, [[Edsger Dijkstra]]), adalah sebuah algoritmaalgoritme rakus (''greedy algorithm'') yang dipakai dalam memecahkan permasalahan jarak terpendek (''shortest path problem'') untuk sebuah [[graf]] berarah (''directed graph'') dengan bobot-bobot sisigaris (''edge weights'') yang bernilai tak-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 graf melambangkan kota-kota dan bobot sisi (''edge weights'')garis melambangkan jarak antara kota-kota tersebut, maka algoritmaalgoritme Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.
 
OngkosBiaya (''cost'') dari sebuah sisigaris dapat dianggap sebagai jarak antara dua ''vertex''simpul, yaitu jumlah jarak semua sisigaris dalam jalur 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>''.▼
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''.
1 '''functionfungsi''' Dijkstra(G''Graf'', w, s''asal''):▼
 
2 ''Q'' adalah himpunan titik
Bobot (''weights'') dari semua sisi dihitung dengan fungsi
3
''w'': ''E'' → [0, ∞)
4 '''untuk setiap''' titik ''v'' dalam ''Graf'':
jadi ''w''(''u'',''v'') adalah jarak tak-negatif dari vertex ''u'' ke vertex ''v''.
5 jarak[''v''] ← tak hingga
 
6 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''.
7 tambahkan ''v'' ke dalam ''Q''
 
8 jarak[''asal''] ← 0;
== Pseudocode ==
9
▲ 1 '''function''' Dijkstra(G, w, s)
10 '''selama''' ''Q'' '''tidak''' kosong:
2 '''for each''' vertex v in V[G] ''// Initializations''
11 3 ''u'' ← titik ddalam ''Q'' dengan nilai jarak[v''u''] := infinityterkecil
12 4 hapus ''u'' dari previous[v] := undefined''Q''
13
5 d[s] := 0 ''// Distance from s to s''
14 '''untuk setiap''' tetangga ''v'' dari ''u'': // hanya ''v'' yang masih dalam ''Q''
6 S := empty set
15 ''alt'' ← jarak[''u''] + jarak_antara(''u'', ''v'')
7 Q := V[G] ''// Set of all vertices''
16 '''jika''' ''alt'' < jarak[''v'']:
8 '''while''' Q is not an empty set ''// The algorithm itself''
17 9 u := Extract_Min(Q) jarak[''v''] ← ''alt''
1018 S := S union { sebelum[''v''] ← ''u}''
19
11 '''for each''' edge (u,v) outgoing from u
20 '''kembalikan''' jarak[], sebelum[]
12 '''if''' d[u] + w(u,v) < d[v] ''// Relax (u,v)''
13 d[v] := d[u] + w(u,v)
14 previous[v] := u
 
== 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&ndash;601595–601.
 
== Lihat jugapula ==
* [[Breadth-first search]]
* [[Open shortest path first]]
Baris 43 ⟶ 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 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://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] {{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:AlgoritmaAlgoritme|Dijkstra]]
 
[[bg:Алгоритъм на Дейкстра]]
[[cs:Dijkstrův algoritmus]]
[[de:Dijkstra-Algorithmus]]
[[en:Dijkstra's algorithm]]
[[es:Algoritmo de Dijkstra]]
[[fi:Dijkstran algoritmi]]
[[fr:Algorithme de Dijkstra]]
[[he:אלגוריתם דייקסטרה]]
[[it:Algoritmo di Dijkstra]]
[[ja:ダイクストラ法]]
[[ko:데이크스트라 알고리즘]]
[[lt:Dijkstros algoritmas]]
[[nl:Kortstepadalgoritme]]
[[no:Dijkstras algoritme]]
[[pl:Algorytm Dijkstry]]
[[pt:Algoritmo de Dijkstra]]
[[ru:Алгоритм Дейкстры]]
[[sk:Dijkstrov algoritmus]]
[[sl:Dijkstrov algoritem]]
[[sr:Дијкстрин алгоритам]]
[[sv:Dijkstras algoritm]]
[[uk:Алгоритм Дейкстри]]
[[vi:Thuật toán Dijkstra]]
[[zh:Dijkstra算法]]
Diperoleh dari "https://wiki-indonesia.club/wiki/Algoritma_Dijkstra"