Algoritma Djikstra

Algoritma djikstra adalah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek ( Shortest Path problem ) untuk sebuah directed graph yang tidak mempunyai bobot bernilai negatif.

Algoritma ini berbasis pada representasi graph dalam adjacency matrix. Dalam hal ini, adjacency matrix cukup menguntungkan sebab ia tidak hanya menemukan jalur terpendek dari satu simpul ke simpul lainnya, tetapi juga dapat menemukan jalur terpendek dari suatu simpul ke semua simpul lainnya.

Contoh penggunaan algoritma djikstra untuk graph :

 

Jarak terpendek dari A ke H :

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)= ∞.
Minimum di b, maka jalur yang di dapat ( a,b )

Iterasi 2

Posisi awal di 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 + 10 } = 14
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 + ∞ } = ∞
Minimum di d, maka jalur yang di dapat ( a,d )

Iterasi 3

Posisi awal di 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 { 14, 7 + ∞ } = 14
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
Minimum di c, maka jalur yang di dapat (a,c)

Iterasi 4

Posisi awal di c :
d(e) = min { d(e), d(c) + a(c,e) } = min { 14, 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
Minimum di f, maka jalur yang di dapat ( d,f )

Iterasi 5

Posisi awal di 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
Minimum di e, maka jalur yang di dapat ( c,e )

Iterasi 6

Posisi awal di 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
Minimum di g, maka jalur yang di dapat ( e,g )

Iterasi 7

Posisi awal di 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
Minimum di i, maka jalur yang di dapat ( d,i )

Iterasi 8

Posisi awal di i :
d(h) = min { d(h), d(i)+ a(i,h) } = min { 24, 19 + 6 } = 24
Minimum di h, iterasi dihentikan maka jalur yang di dapat ( f,h )

Jarak terpendek A ke H

Jadi jalur terpendek dari a – h yang di peroleh adalah ( a,d ), ( d,f ), ( f,h ) dengan panjang 7+2+15 = 24