36
Jika
dimisalkan
u
i
adalah
jarak
terpendek
dari
node
awal
ke
node
ke-i,
dan ditentukan kalau d
ij
(
=
0
)
merupakan panjang jalur
antara node ke-i dengan
node
ke-j,
maka
algoritma
untuk
menentukan
label
node
penerus
berikutnya
dapat dirumuskan menjadi (Taha, 2003, p225) :
[u
j
,i] = [u
j
+
d
ij
, i] , d
ij
=
0
Label
untuk
node
awal
adalah
[
0,
-
],
menyatakan
kalau
node
tersebut
tidak
memiliki predecessor.
Label node
dalam Dijkstra terbagi
menjadi dua
tipe,
yaitu temporary
dan
permanent.
Node
yang
temporary
akan
diubah
menjadi permanent
ketika
rute
yang
terpendek
telah
ditemukan.
Jika
tidak
ada
rute
terbaik
yang
dapat
ditemukan pula, maka status temporary juga akan berubah menjadi permanent.
Langkah 0. Labelkan node awal menjadi permanent [ 0, - ]. Nilai i adalah 1.
Langkah
i.
(a)
Hitung temporary
label [ u
i
+
d
ij
,
i
]
untuk setiap node j
yang
dapat dicapai dari node ke-i, yang belum dilabelkan permanent. Jika
node j
telah dilabelkan dengan [ u
j
,
k
]
melalui node
lain
(
k
), dan
jika u
i
+ d
ij
< u
j
, ubah nilai [u
j
, k] dengan [ u
i
+ d
ij
, i ].
(b)
Jika
semua node
telah
menjadi permanent,
maka proses
selesai.
Jika
belum,
maka
pilih
label
[ur
,
s]
yang
memiliki
jarak
terpendek
(=ur) di antara
label
yang temporary. Nilai
i
=
r, dan
ulangi langkah
ke-i.
 |