Algoritma Dijkstra: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k Robot: Cosmetic changes |
k Hysocc memindahkan halaman Algoritme Dijkstra ke Algoritma Dijkstra dengan menimpa pengalihan lama |
||
(38 revisi perantara oleh 27 pengguna tidak ditampilkan) | |||
Baris 1:
{{terjemah|Inggris}}
[[Berkas:Dijkstra_Animation.gif|jmpl|Algoritme Dijkstra]]
'''
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 ==
Baris 35 ⟶ 34:
* [[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
* [[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
* [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:
|