Algoritma Dijkstra: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k Bot: penggantian teks otomatis (-algoritma, +algoritme) |
k Hysocc memindahkan halaman Algoritme Dijkstra ke Algoritma Dijkstra dengan menimpa pengalihan lama |
||
(8 revisi perantara oleh 6 pengguna tidak ditampilkan) | |||
Baris 1:
{{terjemah|Inggris}}
[[Berkas:Dijkstra_Animation.gif|
'''Algoritme Dijkstra''', (dinamai menurut penemunya, seorang ilmuwan komputer, [[Edsger Dijkstra]]), adalah sebuah algoritme rakus (''greedy algorithm'') yang dipakai dalam memecahkan permasalahan jarak terpendek (''shortest path problem'') untuk sebuah [[graf]] berarah (''directed graph'') dengan bobot-bobot
Misalnya, bila
== Kode semu ==
2 ''Q'' adalah himpunan titik
3
4 '''untuk setiap''' titik ''v'' dalam ''Graf'':
▲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'', algoritme ini menghitung jarak terpendek dari ''s'' ke ''t''.
8 jarak[''asal''] ← 0;
9
▲ '''function''' Dijkstra(''Graph'', ''source''):
11 ''u'' ← titik dalam ''Q'' dengan nilai jarak[''u''] terkecil
13
14 '''
17
18 sebelum[''v'']
19
20 '''kembalikan''' jarak[], sebelum[]
▲ remove ''u'' from ''Q'' ;
▲ '''if''' dist[''u''] = infinity:
▲ ''alt'' := dist[''u''] + dist_between(''u'', ''v'') ;
▲ dist[''v''] := ''alt'' ;
▲ previous[''v''] := ''u'' ;
▲ '''end if'''
== Rujukan ==
Baris 58 ⟶ 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]
|