26
database.
Entity
dapat
berupa
orang,
tempat,
barang,
konsep,
atau
event.
Attribut adalah
properti yang mendeskripsikan beberapa aspek dari objek yang ingin kita
record dan
relationship adalah asosiasi antar entity.
2.8 Shortest Pathfinding
Penggunaan
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 sedikit. Jika edge
memiliki
nilai,
maka shortest path
merupakan path dengan
nilai
akumulasi
minimum dari
semua edge pada path.
Shortest path problem berbeda dengan minimum spanning tree problem. Minimum
spanning tree problem bertujuan untuk mencari tree termurah yang menghubungkan semua
vertex dalam tree. Sedangkan, Shortest path problem bertujuan
untuk
mencari lintasan
termurah
di
antara
beberapa vertex.
Permasalahan
yang
terjadi
pada network
dapat
ditransformasikan
ke
dalam Shortest
path
problem,
seperti
permasalah
transportasi
dan
komunikasi di dalam network.
Secara
umum algoritma
shortest
pathfinding
dapat digolongkan
menjadi dua jenis,
yaitu :
1. Algoritma Uniformed Search
Merupakan
algoritma
yang
tidak
memiliki
keterangan
tentang
jarak atau
biaya dari path dan tidak memiliki pertimbangan akan path mana yang lebih
baik.
Yang
termasuk dalam algoritma
ini
antara
lain algoritma Breath-First
Search.
 |