Algoritma Dijkstra: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
→Pseudocode: Update code |
k Hysocc memindahkan halaman Algoritme Dijkstra ke Algoritma Dijkstra dengan menimpa pengalihan lama |
||
(13 revisi perantara oleh 9 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'':
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''.
8 jarak[''asal''] ← 0;
9
▲ 1 '''function''' Dijkstra(''Graph'', ''source''):
11 ''u'' ← titik dalam ''Q'' dengan nilai jarak[''u''] terkecil
13
14
17
19
20 '''kembalikan''' jarak[], sebelum[]
▲ 13 remove ''u'' from ''Q'' ;
▲ 14 '''if''' dist[''u''] = infinity:
▲ 20 ''alt'' := dist[''u''] + dist_between(''u'', ''v'') ;
▲ 22 dist[''v''] := ''alt'' ;
▲ 26 '''end for'''
== 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 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
* [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:
|