STUDI DAN IMPLEMENTASI PERSOALAN LINTASAN TERPENDEK SUATU GRAF

STUDI DAN IMPLEMENTASI PERSOALAN LINTASAN TERPENDEK SUATU GRAF DENGAN ALGORITMA DIJKSTRA DAN ALGORITMA BELLMAN-FORD

DOWNLOAD MAKALAH LENGKAP DI SINI

Abstrak
Makalah ini membahas tentang studi dan implementasi persoalan lintasan terpendek suatu graf dengan algoritma dijkstra dan algoritma Bellman-Ford. Lintasan terpendek merupakan bagian dari teori graf. Jika diberikan sebuah graf berbobot, masalah jarak terpendek adalah bagaimana kita mencari sebuah jalur pada graf yang meminimalkan jumlah bobot sisi pembentuk jalur tersebut. Persoalan ini adalah persoalan optimasi, dimana kita akan mencari beberapa alternatif solusi penyelesaian yang paling efektif dan mangkus dari masalah penentuan lintasan terpendek pada suatu graf.
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.
Algoritma Dijkstra merupakan salah satu algoritma yang digunakan untuk memecahkan permasalahan lintasan terpendek yang terdapat pada suatu graf . Algoritma ini digunakan pada graf berbobot dengan syarat bobot dari masing-masing sisi haruslah bernilai positif (>=0). Algoritma Bellman-Ford juga merupakan salah satu algoritma yang digunakan untuk memecahkan permasalahan lintasan terpendek yang terdapat pada suatu graf. Algoritma ini digunakan pada graf berbobot dengan bobot yang dapat bernilai positif maupun bernilai negatif. Apabila kita hendak mencari lintasan terpendek dari suatu graf berbobot yang terdapat sisi yang berbobot negatif kita dapat menggunakan algoritma Bellman-Ford, sedangkan apabila kita menemui suatu graf berbobot yang setiap sisinya berbobot positif maka kita dapat menggunakan algoritma Bellman-Ford atau algoritma dijkstra, beberapa analisa pun menunjukkan beberapa keuntungan dan kelemahan dari kedua algoritma tersebut.

Kata kunci: graf, graf berbobot, lintasan, shortest pah problem, algoritma dijkstra, algoritma bellman-ford, pathing algorithm.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: