Algoritma Djikstra

Algoritma Djikstra digunakan untuk mencari jarak terpendek untuk sebuah graf berarah dengan bobot-bobot sisi yang bernilai tak-negatif. Dalam kasus ini, carilah jarak terpendek dari A ke H. Penyelesainnya adalah sebagai berikut:

Iterasi 1

Posisi awal di simpul a

d(a) = 0 , d(b) = 4, d(c) = 8, d(d) = 7, d(e) = ∞, d(f) = ∞, d(g) = ∞, d(h) = ∞, d(i) = ∞

Minimal di b, maka jalur yang didapat ( a, b ).

Iterasi 2

Posisi awal di simpul b.

d(c) = min { d(c) , d(b) + a(b, c) } = min { 8 , 4 + ∞ } = 8

d(d) = min { d(d) , d(b) + a(b, d) } = min { 7 , 4 + 4 } = 7

d(e) = min { d(e) , d(b) + a(b, e) } = min { ∞ , 4 + ∞ } = ∞

d(f) = min { d(f) , d(b) + a(b, f) } = min { ∞ , 4 + ∞ } = ∞

d(g) = min { d(g) , d(b) + a(b, g) } = min { ∞ , 4 + ∞ } = ∞

d(h) = min { d(h) , d(b) + a(b, h) } = min { ∞ , 4 + ∞ } = ∞

d(i) = min { d(i) , d(b) + a(b, i) } = min { ∞ , 4 + ∞ } = ∞

Minimal di d, maka jalur yang didapat ( b, d ).

Iterasi 3

Posisi awal di simpul d.

d(c) = min { d(c) , d(d) + a(d, c) } = min { 8 , 7 + ∞ } = 8

d(e) = min { d(e) , d(d) + a(d, e) } = min { ∞ , 7 + ∞ } = ∞

d(f) = min { d(f) , d(d) + a(d, f) } = min { ∞ , 7 + 2 } = 9

d(g) = min { d(g) , d(d) + a(d, g) } = min { ∞ , 7 + ∞ } = ∞

d(h) = min { d(h) , d(d) + a(d, h) } = min { ∞ , 7 + ∞ } = ∞

d(i) = min { d(i) , d(d) + a(d, i) } = min { ∞ , 7 + 12 } = 19

Minimal di c, maka jalur yang didapat ( a, c ).

Iterasi 4

Posisi awal di simpul c.

d(e) = min { d(e) , d(c) + a(c, e) } = min { ∞ , 8 + 3 } = 11

d(f) = min { d(f) , d(c) + a(c, f) } = min { 9 , 8 + ∞ } = 9

d(g) = min { d(g) , d(c) + a(c, g) } = min { ∞ , 8 + 14 } = 22

d(h) = min { d(h) , d(c) + a(c, h) } = min { ∞ , 8 + ∞ } = ∞

d(i) = min { d(i) , d(c) + a(c, i) } = min { 19 , 8 + ∞ } = 19

Minimal di f, maka jalur yang didapat ( d, f ).

Iterasi 5

Posisi awal di simpul f.

d(e) = min { d(e) , d(f) + a(f, e) } = min { 11 , 9 + 5 } = 11

d(g) = min { d(g) , d(f) + a(f, g) } = min { 22 , 9 + ∞ } = 22

d(h) = min { d(h) , d(f) + a(f, h) } = min { ∞ , 9 + 15 } = 24

d(i) = min { d(i) , d(f) + a(f, i) } = min { 19 , 9 + ∞ } = 19

Minimal di e, maka jalur yang didapat ( c, e ).

Iterasi 6

Posisi awal di simpul e.

d(g) = min { d(g) , d(e) + a(e, g) } = min { 22 , 11 + 8 } = 19

d(h) = min { d(h) , d(e) + a(e, h) } = min { 24 , 11 + ∞ } = 24

d(i) = min { d(i) , d(e) + a(e, i) } = min { 19 , 11 + ∞ } = 19

Minimal di g, maka jalur yang didapat ( e, g ).

Iterasi 7

Posisi awal di simpul g.

d(h) = min { d(h) , d(g) + a(g, h) } = min { 24 , 19 + 7 } = 24

d(i) = min { d(i) , d(g) + a(g, i) } = min { 19 , 19 + ∞ } = 19

Minimal di i, maka jalur yang didapat ( d, i ).

Iterasi 8

Posisi awal di simpul i.

d(h) = min { d(h) , d(i) + a(i, h) } = min { 24 , 19 + 6 } = 24

Minimal di h, maka jalur yani didapat ( f, h )