ALGORITMA DJIKSTRA

ALGORITMA DJIKSTRA

Algoritma Djikstra digunakan untuk menentukan lintasan terpendek pada graph bobot.

Input   : Graph bobot G dengan s, t ∈ v(G)

Step 1  : Label titik s dengan ⋋(s) = 0 dan  verteks v ∈ G – {s} diberi label ⋋(v) = ∞.

            Tulis T = v(G).

Step 2  : Misalkan u ∈ T dengan ⋋(u) minimum.

Setp 3  : Jika u = t maka STOP dan beri pesan “:p lintasan terpendek dari s ke t adalah ⋋(t)”

Step 4  :  edge e=(u , v), ganti label v dengan ⋋(v) = min {⋋(v) , ⋋(u) + W(u , v)}

Step 5 : Tulis T = T – {u} dan pergi ke step 2.