SINGLE-SOURCE SHORTEST PATH PADA GRAF BERBOBOT MENGGUNAKAN ALGORITMA DIJKSTRA DAN BELLMAN-FORD

Abstract

Graf adalah sebuah teori matematika yang sangat tua, dan masih digunakan hingga hari ini. Graf ini memiliki  karakteristik yang menarik sehingga dapat merepresentasikan berbagai macam masalah. Algoritma untuk perhitungan jarak terpendek antar graf dengan sisi yang memiliki bobot ada bermacam-macam. Pada makalah ini akan dibahas dua macam algoritma, yaitu algoritma Dijkstra dan Algoritma Bellman-Ford. Selain membahas karakteristik dari dua algoritma tersebut, akan dibahas juga perbedaan dari dua algoritma tersebut. Pencarian lintasan terpendek merupakan salah satu persoalan dalam teori graf. Persoalan ini bisa diselesaikan dengan algoritma Dijkstra. Aplikasi teori graf dapat kita saksikan sendiri bila mengendarai kendaraan bermotor di wilayah kota-kota besar pada umumnya. Kita punya banyak alternatif jalan untuk sampai ke tujuan.Namun ada jalan yang satu arah, ada titik-titik kemacetan, ada jam-jam sibuk. Contoh dalam kehidupan sehari-hari adalah masalah kemacetan lalu lintas yang sering terjadi selama perjalanan, sering mengganggu kegiatan kita sehari-hari.Setiap manusia ingin sampai ke tujuan dengan tepat waktu.Tetapi, sering kali kemacetan menyebabkan keinginan manusia terganggu.Dengan pemahaman tentang teori graf, para ahli transportasi mengatur agar lampu lalu lintas menyala dengan warna dan saat yang tepat. Selain itu, pengetahuan tentang teori graf juga diaplikasikan dalam pengaturan jalur penerbangan agar tidak ada pesawat yang bersimpangan, pengaturan jalur telekomunikasi ketika ada pelanggan yang melakukan panggilan telepon, pengaturan jalur pelayaran, serta segala sistem yang berkaitan dengan “titik” dan “garis”. Titik (vertex) dapat digunakan.untuk melambangkan kota, pelabuhan, stasiun, terminal atau airport. Oleh karena itu, dibutuhkan suatu cara untuk menanggulangi gangguan tersebut. Untuk mencapai suatu tempat tujuan dengan waktu yang lebih cepat, kita akan mencari lintasan terpendek dari tempat asal ke tempat tujuan. Hasil yang didapatkan bahwa kompleksitas algoritma dari algoritma Djikstra adalah O(1½ N2).Jika algoritma Djikstra dimodifikasi dengan metodeFord, kompleksitas dari algoritma ini akan meningkatsecara polinomial. Hal ini disebabkan setiap simpul pada graf maksimum akan dikunjungi sebanyak N – 1 kali.Akibat dari hal ini adalah peningkatan kompleksitas sebanyak N – 1 kali. Jadi, O(1 ½ N2) X (N – 1) = O(1 ½N3). Jadi setelah algoritma Djikstra dimodifikasi dengan menggunakan metode Ford, kompleksitasnya adalah O(1½ N3).