# Algoritma Dijkstra

### Dari Wikipedia Indonesia, ensiklopedia bebas berbahasa Indonesia.

| Artikel ini belum atau baru diterjemahkan sebagian dari bahasa Inggris. Bantulah Wikipedia untuk melanjutkannya. Lihat panduan penerjemahan Wikipedia.

Algoritma Dijkstra, dinamai menurut penemunya, Edsger Dijkstra, adalah sebuah algoritma rakus (greedy algorithm) 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.

## [sunting] 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

## [sunting] 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.

## [sunting] Lihat juga

- Breadth-first search
- Open shortest path first

## [sunting] Pranala luar

- Teori Jalan Terpendek Dijkstra oleh Jeremy Siek, dari Universitas Indiana
- Animation of Dijkstra's algorithm
- The Boost Graph Library (BGL)
- Javascript Dijkstra's Algorithm
- Interactive Implementation of Dijkstra's Algorithm
- Shortest Path Problem: Dijkstra's Algorithm
- Dijkstra's Algorithm Applet

Diperoleh dari "http://id.wikipedia.org../../../a/l/g/Algoritma_Dijkstra_2427.html"

Kategori: Artikel yang perlu diterjemahkan dari bahasa Inggris • Algoritma

##### Views

- Artikel
- Pembicaraan
- Revisi sekarang

##### Cari

##### Bahasa lain

- Български
- Česky
- Deutsch
- English
- Español
- Suomi
- Français
- עברית
- Italiano
- 日本語
- 한국어
- Lietuvių
- Nederlands
- ‪Norsk (bokmål)‬
- Polski
- Português
- Русский
- Slovenščina
- Српски / Srpski
- Svenska
- Українська
- Tiếng Việt
- 中文