Sebuah graf dengan bilangan-bilangan pada rusuk-rusuknya disebut graf berbobot (weighted graph). Dalam sebuah graf berbobot, panjang lintasan adalah jumlah bobot rusuk-rusuk dalam lintasan. Dalam bahasan ini bobot setiap lintasan tidak hanya merepresentasikan panjang lintasan saja, tetapi juga merepresentasikan tingkat kepadatan/ kemacetan jalan/lintasan. Jadi akumulasi dari panjang jalan dari suatu titik/tempat acuan di jalan yang nyata ke titik berikutnya dan tingkat kepadatan pada jalan tersebut merupakan bobot untuk setiap lintasan.
[gambar graf berbobot tak berarah.]
Semakin besar bobot suatu lintasan maka akan menghabiskan waktu yang semakin lama untuk melalui lintasan itu. Jadi bobot pada graf berbanding lurus dengan waktu tempuh dan efektifitas jalan untuk dilalui.
Untuk merepresentasikan gambar jalan yang diterima dari satelit pada perangkat navigasi GPS maka kedua bentuk graf yang sudah dibahas di atas perlu digabung sehingga membentuk graf berbobot dan berarah.
Dengan graf berbobot dan berarah maka kedua masalah utama untuk merepresentasikan lintasan atau jalan dapat diatasi, yaitu masalah jarak/panjang lintasan dan tingkat kepadatan jalan. Sekarang masih ada satu masalah yang sangat penting untuk dicari solusinya yaitu mengambil keputusan jalan mana yang akan dipilih. Hal tersebut akan dilakukan pendekatan dengan menggunakan pohon keputusan.
referensi : Inggriani Liem, “Draft Diktat Struktur Data”, Institut Teknologi Bandung, Bandung, 2008
Tidak ada komentar:
Posting Komentar
Tinggalkan Komentar :