Edsger Dijkstra - Algoritma Jalan Terpendek

Edsger Dijkstra - Algoritma Jalan Terpendek

Edsger Wybe Dijkstra (lahir di Rotterdam, Holland Selatan, Belanda, 11 Mei 1930 – meninggal di Nuenen, Gerwen en Nederwetten, Brabant Utara, Belanda, 6 Agustus 2002 pada umur 72 tahun) adalah seorang ilmuwan komputer asal Belanda.

Dijkstra awalnya belajar fisika teori di Universitas Leiden. Kemudian pada awal 1970-an ia bekerja sebagai anggota peneliti di Burroughs Corporation. Ia juga bekerja di Universitas Teknologi Eindhoven di Belanda dan akhirnya ia menjabat sebagai ketua Schlumberger Centennial dalam bidang Ilmu Komputer di Universitas Texas di Austin, Amerika Serikat. Ia pensiun pada tahun 2000.

Satu dari sekian banyak sumbangannya di dalam ilmu komputer, adalah algoritma jalan terpendek (shortest path-algorithm), atau dikenal juga sebagai Algoritma Dijkstra. Ia menerima Turing Award pada tahun 1972.

Penghargaan Turing (bahasa Inggris: A.M. Turing Award) adalah sebuah penghargaan yang diberikan setiap tahun oleh Association for Computing Machinery kepada mereka yang terpilih karena kontribusinya yang bersifat teknik kepada dunia ilmu komputer.

Penghargaan ini dinamakan berdasarkan nama Alan Mathison Turing (1912–1954), seorang matematikawan dari Inggris yang dianggap sebagai salah satu bapak ilmu komputer modern.

Algoritma Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.

Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.

Input algoritma 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.

Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua tepi disebut E.

Bobot (weights) dari semua sisi dihitung dengan fungsi w: E → [0, ∞)

jadi w(u,v) adalah jarak tak-negatif dari vertex u ke vertex v.

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.

Pseudocode

1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity ; // Unknown distance function from
4 // source to v
5 previous[v] := undefined ; // Previous node in optimal path
6 end for //
from source
7
8 dist[source] := 0 ; // Distance from source to source
9 Q := the set of all nodes in Graph ; // All nodes in the graph are
10 // unoptimized - thus are in Q
11 while Q is not empty: // The main loop
12 u := vertex in Q with smallest distance in dist[] ; // Start node in first case
13 remove u from Q ;
14 if dist[u] = infinity:
15 break ; // all remaining vertices are
16 end if // inaccessible from source
17
18 for each neighbor v of u: // where v has not yet been
19 // removed from Q.
20 alt := dist[u] + dist_between(u, v) ;
21 if alt < dist[v]: // Relax (u,v,a) 22 dist[v] := alt ; 23 previous[v] := u ; 24 decrease-key v in Q; // Reorder v in the Queue 25 end if 26 end for 27 end while 28 return dist; Rujukan : E. W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269–271