Algoritma Dijkstra: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k ←Suntingan 61.5.110.224 (bicara) dikembalikan ke versi terakhir oleh SieBot |
k Hysocc memindahkan halaman Algoritme Dijkstra ke Algoritma Dijkstra dengan menimpa pengalihan lama |
||
(24 revisi perantara oleh 17 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 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:
|