Wikipedia

Algoritma Dijkstra: Perbedaan antara revisi

Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
EmausBot (bicara | kontrib)
Bot
578.591 suntingan
k Bot: Migrasi 36 pranala interwiki, karena telah disediakan oleh Wikidata pada item d:Q8548
k Hysocc memindahkan halaman Algoritme Dijkstra ke Algoritma Dijkstra dengan menimpa pengalihan lama
 
(12 revisi perantara oleh 8 pengguna tidak ditampilkan)
Baris 1:
{{terjemah|Inggris}}
[[Berkas:Dijkstra_Animation.gif|thumbjmpl|AlgoritmaAlgoritme 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(''GraphGraf'', ''sourceasal''):▼
 
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''.
22 5 distjarak[''v''] :=← ''alt''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''.
13 7 remove tambahkan ''uv'' fromke dalam ''Q'' ;▼
 
8 jarak[''asal''] ← 0;
== Pseudocode ==
9
▲ 1 '''function''' Dijkstra(''Graph'', ''source''):
2 10 '''for eachselama''' vertex ''vQ'' in ''Graph'tidak': ''// Initializations''kosong:
11 ''u'' ← titik dalam ''Q'' dengan nilai jarak[''u''] terkecil
3 dist[''v''] := infinity ; ''// Unknown distance function from''
2612 hapus ''u''end fordari ''Q''▼
4 ''// source to v''
13
5 previous[''v''] := undefined ; ''// Previous node in optimal path
14 6 '''enduntuk forsetiap''' tetangga ''v'' dari ''u'': // hanya ''v'' yang masih dalam ''// from sourceQ''
2015 ''alt'' :=← distjarak[''u''] + dist_betweenjarak_antara(''u'', ''v'') ;▼
7
1416 '''ifjika''' dist[''ualt''] =< infinityjarak[''v'']:▼
8 dist[''source''] := 0 ; ''// Distance from source to source''
17 9 ''Q'' := the set of all nodes in jarak[''Graphv''] ; ← ''// All nodes in the graph arealt''
10 18 sebelum[''v''] ← ''// unoptimized - thus are in Qu''
19
11 '''while''' ''Q'' '''is not''' empty: ''// The main loop''
20 '''kembalikan''' jarak[], sebelum[]
12 ''u'' := vertex in ''Q'' with smallest distance in dist[] ; ''// Start node in first case''
▲ 13 remove ''u'' from ''Q'' ;
▲ 14 '''if''' dist[''u''] = infinity:
15 '''break''' ; ''// all remaining vertices are''
16 '''end if''' ''// inaccessible from source''
17
18 '''for each''' neighbor ''v'' of ''u'': ''// where v has not yet been''
19 ''// removed from Q.''
▲ 20 ''alt'' := dist[''u''] + dist_between(''u'', ''v'') ;
21 '''if''' ''alt'' < dist[''v'']: ''// Relax (u,v,a)''
▲ 22 dist[''v''] := ''alt'' ;
23 previous[''v''] := ''u'' ;
24 decrease-key ''v'' in ''Q''; ''// Reorder v in the Queue''
25 '''end if'''
▲ 26 '''end for'''
27 '''end while'''
28 '''return''' dist;
 
== 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.
Hendri Antomy--Master computer
 
== Lihat pula ==
Baris 59 ⟶ 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]]
Diperoleh dari "https://wiki-indonesia.club/wiki/Algoritma_Dijkstra"