Algoritma Dijkstra: Perbedaan antara revisi
k +kat |
k robot Adding: uk:Алгоритм Дейкстри |
||
Baris 47: | Baris 47: | ||
[[en:Dijkstra's algorithm]] |
[[en:Dijkstra's algorithm]] |
||
[[es:Algoritmo de Dijkstra]] |
[[es:Algoritmo de Dijkstra]] |
||
⚫ | |||
[[fr:Algorithme de Dijkstra]] |
[[fr:Algorithme de Dijkstra]] |
||
⚫ | |||
⚫ | |||
[[he:אלגוריתם דייקסטרה]] |
[[he:אלגוריתם דייקסטרה]] |
||
⚫ | |||
⚫ | |||
⚫ | |||
[[lt:Dijkstros algoritmas]] |
[[lt:Dijkstros algoritmas]] |
||
[[nl:Kortstepadalgoritme]] |
[[nl:Kortstepadalgoritme]] |
||
⚫ | |||
[[pl:Algorytm Dijkstry]] |
[[pl:Algorytm Dijkstry]] |
||
[[pt:Algoritmo de Dijkstra]] |
[[pt:Algoritmo de Dijkstra]] |
||
Baris 59: | Baris 60: | ||
[[sl:Dijkstrov algoritem]] |
[[sl:Dijkstrov algoritem]] |
||
[[sr:Дијкстрин алгоритам]] |
[[sr:Дијкстрин алгоритам]] |
||
⚫ | |||
[[sv:Dijkstras algoritm]] |
[[sv:Dijkstras algoritm]] |
||
[[uk:Алгоритм Дейкстри]] |
|||
[[vi:Thuật toán Dijkstra]] |
[[vi:Thuật toán Dijkstra]] |
||
[[zh:Dijkstra算法]] |
[[zh:Dijkstra算法]] |
Revisi per 18 November 2006 06.54
Artikel ini perlu diterjemahkan dari bahasa Inggris ke bahasa Indonesia. |
Algoritma Dijkstra, dinamai menurut penemunya, Edsger Dijkstra, adalah greedy algorithm yang memecahkan shortest path problem untuk sebuah directed graph dengan edge weights yang tidak negatif.
Misalnya, bila vertices dari sebuah graph melambangkan kota-kota dan edge weights melambangkan jarak antara kota-kota tersebut, algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.
Input algoritma ini adalah sebuah weighted directed graph G dan sebuah source vertex s dalam G. V adalah himpunan semua vertices dalam graph G. Setiap edge dari graph ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua edge disebut E. Weights dari edges dihitung dengan fungsi w: E → [0, ∞); jadi w(u,v) adalah jarak non-negatif dari vertex u ke vertex v. Cost dari sebuah edge dapat dianggap sebagai jarak antara dua vertex, yaitu jumlah jarak semua edge dalam path tersebut. Untuk sepasang vertex s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t.
Pseudocode
1 function Dijkstra(G, w, s) 2 for each vertex v in V[G] // Initializations 3 d[v] := infinity 4 previous[v] := undefined 5 d[s] := 0 // Distance from s to s 6 S := empty set 7 Q := V[G] // Set of all vertices 8 while Q is not an empty set // The algorithm itself 9 u := Extract_Min(Q) 10 S := S union {u} 11 for each edge (u,v) outgoing from u 12 if d[u] + w(u,v) < d[v] // Relax (u,v) 13 d[v] := d[u] + w(u,v) 14 previous[v] := u
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.