Graf adalah salah satu cabang matematik yang
dapat digunakan dalam menyelesaikan masalah
melibatkan perkiraan yang kompleks. Diantara
penggunaannya yang populer adalah penganalisaan
sistem rangkaian jalan raya melalui kaidah teori graf.
Maklumat anggaran berkaitan dengan jarak, cost, dan
waktu tempuh perjalanan pada rute terpendek yang
akan turut disenaraikan melalui sistem yang
dibangun. Algoritma Floyd Warshall digunakan untuk
proses pencarian rute terpendek pada lokasi awal dan
akhir yang dikehendaki pengguna sistem.
Persoalan mencari lintasan terpendek di dalam graf
merupakan persoalan salah satu optimasi. Graf yang
digunakan dalam pencarian lintasan terpendek adalah graf
berbobot (weighted graph), yaitu graf yang setiap sisinya
diberikan suatu nilai atau bobot. Bobot pada sisi graf
dapat menyatakan jarak antar kota, waktu pengiriman
pesan, ongkos pembangunan, dan sebagainya. Asumsi
yang kita gunakan adalah bahwa semua bobot bernilai
positif. Kata “terpendek” berbeda-beda maknanya
bergantung pada tipikal persoalan yang akan diselesaikan.
Namun, secara umum “terpendek” berarti meminimasi
bobot pada suatu lintasan di dalam graf.
Download File
Tidak ada komentar:
Posting Komentar