43
daerah
yang
akan
dilalui
sehingga
algoritma
ini
termasuk
algoritma
yang
menggunakan
metode
greedy
Metode
greedy
adalah
metode
yang
mengangap
semua
titik
memilik
kemungkinan
(Nilsson,
!980). Algoritma
Dijkstra
adalah
algoritma A*
yang tidak
memiliki
heuristic
karena
memiliki
fungsi
sebagai
berikut:
f(n)=
g(n)-h(n)
dimana
h(n)=O.
Algoritma
Dijkstra menurut
Horowitz dan
Sahni (1978) adalah
berikut:
{initial
ada!ah
vertex
awa!,
terminal
adalah
vertex
akhir,
dan
semua
vertex
diberi
nilai
sebagai
integer.
Matrix
jarak
diberi nama M.
}
L
Mulai Program
2.
V: =
[semua vertex];
(V
adalah
kumpulan seluruh vertex)
3.
S:
=[initial]; (S
adalah
kumpulan
vertex yang
"diketahui")
4.
T:
=V-S; {T
ada!ah
kumpu!an vertex
yang belum
diketahui jaraknya
5.
D[initial]:
=
0;
{D[x]
adalah
nilai
jarak
dari
vertex
initial,
nilai
yang
dievaluasi
hanya vertex yang
berasal
dari
S}
6. Untuk vertex:=
1
sampaijumlah_vertex lakukan
perulangan
Temp[vertex]: =
9999
.•
akhir perulangan;
{Temp
mewakili
perkiraan
jarak,
dan
diberi
harga
awal
"tak
terhingga")
7. focus : = initial; (kita mulai
dengan initiai vertex sebagi focus)
8.
Selama terminal di
dalam.
T
lakukan
perulangan
9. min:=
9999;
!0.
Untuk vertex:= 1
sampaijumlah_vertex
lakukan.
perulangan
ll. Jika vertex dalam.
T
lakukan
12.
Jika
D[focus]+ M[focus,
vertex]< Temp[vertex]lakukan
13.
Temp[vertex]:= D[focus]
+
M[focus,
vertex] akhir
jika;
 |