38
2.4. Shortest Pathfinding
Tujuan dari
shortest
pathfinding adalah
untuk
menentukan
lintasan
terpendek
dan
termurah
yang
mungkin
dari
vertex
awal
ke
vertex
akhir.
Jika
edge
tidak
memiliki
nilai,
maka
shortest
path
adalah
path
dengan
jumlah edge
yang
paling
sedik:it.
Jika
edge
memiliki nilai,
maka
shortest
path
adalah
path
dengan
nilai
akumu!asi
minimum
dari
semua
edge
pada
path.
Shortest
path
problem
berbeda
dengan
minimum
spanning
tree
problem.
Shortest
path
problem
bertujuan untuk mencari
lintasan termurah
di
antara beberapa vertex,
sedangkan minimum
spanning
tree
problem
bertujuan
untuk
mencari
tree
termurah
yang
menghubungkan
semua
vertex
dalam
tree.
Banyak masalah
pada
network
dapat
ditransformasikan ke
dalam
shortest
path
problem,
seperti
masalah transportasi
dan
komunikasi di
dalam network.
Secara umum
algoritma shortest pathfinding dapat
digolongkan menjadi dua
jenis,
yaitu
!.
Algoritma Uniformed
Search
Adalah
algoritma yang
tidak memiliki
keterangan
tentang
jarak
atau biaya
dari
path dan
tidak
metnilik:i pertimbangan
akan path mana
yang
lebih
baik yang
termasuk
dalam
algoritma ini
antara lain
algoritma Breadth First
Search.
 |