Algoritma Dijkstra: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k Bot: Mengganti Dijksta_Anim.gif dengan Dijkstra_Animation.gif |
k Hysocc memindahkan halaman Algoritme Dijkstra ke Algoritma Dijkstra dengan menimpa pengalihan lama |
||
(14 revisi perantara oleh 10 pengguna tidak ditampilkan) | |||
Baris 1:
{{terjemah|Inggris}}
[[Berkas:Dijkstra_Animation.gif|
'''
Misalnya, bila
== Kode semu ==
2 ''Q'' adalah himpunan titik
3
4 '''untuk setiap''' titik ''v'' dalam ''Graf'':
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;
9
▲ 1 '''function''' Dijkstra(G, w, s)
10 '''selama''' ''Q'' '''tidak''' kosong:
11
12
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
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 ==
Baris 45 ⟶ 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
* [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:
|