Algoritma Djikstra

Berikut adalah graf. Buatlah jalur terpendek dari A ke H dengan menggunakan algoritma djikstra :

Iterasi 1 dari 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,  jalur yang didapat (a,b)

iterasi 2

posisi 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,  jalur yang didapat (a,d)

iterasi3

pasisi 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, jalur yang didapat (a,c)

iterasi 4

posisi 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,  jalur yang didapat (d,f)

iterasi 5

posisi 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+15 =>   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, jalur yang didapat (c,e)

 

iterasi 6

pasisi 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  di g, jalur yang didapat (e,g)

iterasi 7

posisi 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  di i, jalur yang didapat (d,i)

iterasi 8

posisi di i

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

minimum di h. Jalur yang didapat (f,h)

Jalur yang didapat(a,d,f,h) dengan jarak 24