Wikipedia

Algoritma Dijkstra: Perbedaan antara revisi

Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
k FelixJL111 memindahkan halaman Algoritma Dijkstra ke Algoritme Dijkstra: Mengubah kata "algoritma" ke "algoritme" yang lebih baku menurut KBBI
k Hysocc memindahkan halaman Algoritme Dijkstra ke Algoritma Dijkstra dengan menimpa pengalihan lama
 
(6 revisi perantara oleh 4 pengguna tidak ditampilkan)
Baris 2:
[[Berkas:Dijkstra_Animation.gif|jmpl|Algoritme Dijkstra]]
 
'''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 sisigaris (''edge weights'') yang bernilai tak-negatifnonnegatif, ''<math>[0, \infty)</math>''. Input algoritme ini adalah sebuah graf berarah yang berbobot (''weighted directed graph'') <math>G</math> dan sebuah titik asal ''<math>s</math>'' dalam himpunan garis ''<math>V</math>''.
 
Misalnya, bila ''[[vertices]]''titik dari sebuah graf melambangkan kota-kota dan bobot sisi (''edge weights'')garis melambangkan jarak antara kota-kota tersebut, maka algoritme Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.
 
OngkosBiaya (''cost'') dari sebuah sisigaris dapat dianggap sebagai jarak antara dua ''vertex''simpul, yaitu jumlah jarak semua sisigaris dalam jalur tersebut. Untuk sepasang vertextitik ''<math>s</math>'' dan ''<math>t</math>'' dalam ''<math>V</math>'', algoritme ini menghitung jarak terpendek dari ''<math>s</math>'' ke ''<math>t</math>''.▼
Input algoritme ini adalah sebuah graf berarah yang berbobot (''weighted directed graph'') ''G'' dan sebuah sumber ''[[vertex]]'' ''s'' dalam ''G'' dan ''V'' adalah himpunan semua [[vertices]] dalam graph ''G''.
 
== Kode semu ==
Setiap sisi dari graf ini adalah pasangan vertices (''u'',''v'') yang melambangkan hubungan dari ''vertex'' ''u'' ke ''vertex'' ''v''. Himpunan semua tepi disebut ''E''.
1 '''functionfungsi''' Dijkstra(''GraphGraf'', ''sourceasal''):▼
 
2 ''Q'' adalah himpunan titik
Bobot (''weights'') dari semua sisi dihitung dengan fungsi
3
''w'': ''E'' → [0, ∞)
4 '''untuk setiap''' titik ''v'' dalam ''Graf'':
jadi ''w''(''u'',''v'') adalah jarak tak-negatif dari vertex ''u'' ke vertex ''v''.
5 distjarak[''v''] :=← ''alt''tak ;hingga▼
 
6 previoussebelum[''v''] := ''u''← ;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'', algoritme ini menghitung jarak terpendek dari ''s'' ke ''t''.
7 remove tambahkan ''uv'' fromke dalam ''Q'' ;▼
 
8 jarak[''asal''] ← 0;
== Pseudocode ==
9
▲ '''function''' Dijkstra(''Graph'', ''source''):
10 '''for eachselama''' vertex ''vQ'' in ''Graph'tidak': ''// Initializations''kosong:
11 ''u'' ← titik dalam ''Q'' dengan nilai jarak[''u''] terkecil
dist[''v''] := infinity ; ''// Unknown distance function from''
12 hapus ''u''end ifdari ''Q''▼
''// source to v''
13
previous[''v''] := undefined ; ''// Previous node in optimal path
14 '''enduntuk forsetiap''' tetangga ''v'' dari ''u'': // hanya ''v'' yang masih dalam ''// from sourceQ''
15 ''alt'' :=← distjarak[''u''] + dist_betweenjarak_antara(''u'', ''v'') ;▼
16 '''ifjika''' dist[''ualt''] =< infinityjarak[''v'']:▼
dist[''source''] := 0 ; ''// Distance from source to source''
17 ''Q'' := the set of all nodes in jarak[''Graphv''] ; ← ''// All nodes in the graph arealt''
18 sebelum[''v''] ← ''// unoptimized - thus are in Qu''
19
'''while''' ''Q'' '''is not''' empty: ''// The main loop''
20 '''kembalikan''' jarak[], sebelum[]
''u'' := vertex in ''Q'' with smallest distance in dist[] ; ''// Start node in first case''
▲ remove ''u'' from ''Q'' ;
▲ '''if''' dist[''u''] = infinity:
'''break''' ; ''// all remaining vertices are''
'''end if''' ''// inaccessible from source''
'''for each''' neighbor ''v'' of ''u'': ''// where v has not yet been''
''// removed from Q.''
▲ ''alt'' := dist[''u''] + dist_between(''u'', ''v'') ;
'''if''' ''alt'' < dist[''v'']: ''// Relax (u,v,a)''
▲ dist[''v''] := ''alt'' ;
▲ previous[''v''] := ''u'' ;
decrease-key ''v'' in ''Q''; ''// Reorder v in the Queue''
▲ '''end if'''
'''end for'''
'''end while'''
'''return''' dist;
 
== 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 JavascriptJavaScript Dijkstra's Algorithm] {{Webarchive|url=https://web.archive.org/web/20060702173918/http://www.itonsite.co.uk/allanboydproject/section4_2.htm |date=2006-07-02 }}
* [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]
 
Diperoleh dari "https://wiki-indonesia.club/wiki/Algoritma_Dijkstra"