Saat ini banyak sekali algortima-algoritma yang dapat digunakan untuk menyelesaikan persoalan penentuan lintasan terpendek (shortest path problem) dari suatu graf. Solusi yang didapat dari penelusuran algoritma tersebut dapat diberi nama Pathing Algorithm. Ada dua algortima yang cukup terkenal yang bisa digunakaan untuk menyelesaikan persoalan lintasan terpendek, yaitu Algoritma Dijkstra dan Algoritma Bellman-Ford. Tapi yang kami gunakan disini adalah Algoritma Moore.
Graf merupakan model matematika yang sangat kompleks dan rumit, tapi bisa juga menjadi solusi yang sangat bagus terhadap beberapa kasus tertentu. Banyak sekali aplikasi yang menggunakan dengan graf sebagai alat untuk merepresentasikan atau memodelkan persoalan sehinggan persoalan itu dapat diselesaikan dengan baik. Aplikasi-aplikasi tersebut misalnya menentukan lintasan terpendek (the Shortest Path Problem), persoalan pedagang keliling (travelling salesperson problem), persoalan tukang pos Cina (chinese postman problem), pewarnaan graf (graph colouring), Pembuatan system jalan raya satu arah (Making a Road System One-way), menentukan peringkat peserta sebuah turnamen (Rangking the Participants in a tournament), dan masih banyak lagi. Di dalam makalah ini penulis mencoba mengulas tentang salah satu aplikasi graph yaitu tentang persoalan menentukan lintasan terpendek.
Menurut teori Graf, persoalan lintasan terpendek adalah merupakan suatu persoalan untuk mencari lintasan antara dua buah simpul pada graf berbobot yang memiliki gabungan nilai jumlah bobot pada sisi graf yang dilalui dengan jumlah yang paling minimum. Persoalan lintasan terpendek ini pun banyak sekali dijumpai di kehidupan sehari-hari. Aplikasi yang paling sering ditemui adalah pada bidang transportasi dan komunikasi, seperti pada pencarian rute terbaik untuk menempuh dua kota atau untuk mengetahui dan menelusuri proses pengiriman paket data komunikasi dalam suatu jaringan komunikasi agar dihasilkan suatu proses yang paling cepat.
Graf merupakan model matematika yang sangat kompleks dan rumit, tapi bisa juga menjadi solusi yang sangat bagus terhadap beberapa kasus tertentu. Banyak sekali aplikasi yang menggunakan dengan graf sebagai alat untuk merepresentasikan atau memodelkan persoalan sehinggan persoalan itu dapat diselesaikan dengan baik. Aplikasi-aplikasi tersebut misalnya menentukan lintasan terpendek (the Shortest Path Problem), persoalan pedagang keliling (travelling salesperson problem), persoalan tukang pos Cina (chinese postman problem), pewarnaan graf (graph colouring), Pembuatan system jalan raya satu arah (Making a Road System One-way), menentukan peringkat peserta sebuah turnamen (Rangking the Participants in a tournament), dan masih banyak lagi. Di dalam makalah ini penulis mencoba mengulas tentang salah satu aplikasi graph yaitu tentang persoalan menentukan lintasan terpendek.
Menurut teori Graf, persoalan lintasan terpendek adalah merupakan suatu persoalan untuk mencari lintasan antara dua buah simpul pada graf berbobot yang memiliki gabungan nilai jumlah bobot pada sisi graf yang dilalui dengan jumlah yang paling minimum. Persoalan lintasan terpendek ini pun banyak sekali dijumpai di kehidupan sehari-hari. Aplikasi yang paling sering ditemui adalah pada bidang transportasi dan komunikasi, seperti pada pencarian rute terbaik untuk menempuh dua kota atau untuk mengetahui dan menelusuri proses pengiriman paket data komunikasi dalam suatu jaringan komunikasi agar dihasilkan suatu proses yang paling cepat.
Pathing Algorhitm
adalah sebuah algoritma yang digunakan untuk mencari suatu solusi dalam menentukan lintasan terpendek dari suatu graf. Menurut teori Graf, persoalan lintasan terpendek adalah merupakan suatu persoalan untuk mencari lintasan antara dua buah simpul pada graf berbobot yang memiliki gabungan nilai jumlah bobot pada sisi graf yang dilalui dengan jumlah yang paling minimum. Persoalan lintasan terpendek ini pun banyak sekali dijumpai di kehidupan sehari-hari. Aplikasi yang paling sering ditemui adalah pada bidang transportasi dan komunikasi, seperti pada pencarian rute terbaik untuk menempuh dua kota atau untuk mengetahui dan menelusuri proses pengiriman paket data komunikasi dalam suatu jaringan komunikasi agar dihasilkan suatu proses yang paling cepat.
-->ALGORITMA MOORE
- S = 0
- Setiap sisi terdekat = i +1
- Setiap sisi terdekat dengan label 2 = i + 2
- Setiap sisi terdekat dengan label 3 = i + 3
flowchart
Tidak ada komentar:
Posting Komentar