ALGORITMA DIJKSTRA DAN WARSHALL a. Algoritma Djikstra 1.Pengertian Algoritma dijkstra ditemukan oleh seorag ilmuwan computer berkebangsaan Belanda, bernama Edsger Dijkstra. ALGORITMA DIJKSTRA adalah algoritma yang I gunakan untuk mencari lintasan terpndek pada sebuah graf berarah maupun tidak. 2.Cara Kerja Cara kerja Algoritma dijkstra memakai strategi greedy, dimana pada setiap langkah di pilih sisi dengan bobot terkecil yang menghubungkan sebuah simpul yang sudah terpilih dengan simpul yang sudah terpilih dengan simpul lain yang belum terpilih. Algoritma Dijkstra membutuhkan parameter tempat asal dan tempat tujuan. Hasil akhir dari algoritma ini adalah jarak terpendek dari tempat asal ke tempat ujuan beserta rutenya. contoh:
This document is posted to help you gain knowledge. Please leave a comment to let me know what you think about it! Share it to your friends and learn new things together.
Transcript
ALGORITMA DIJKSTRA DAN WARSHALL
a. Algoritma Djikstra
1.Pengertian
Algoritma dijkstra ditemukan oleh seorag ilmuwan computer berkebangsaan Belanda,
bernama Edsger Dijkstra. ALGORITMA DIJKSTRA adalah algoritma yang I gunakan untuk
mencari lintasan terpndek pada sebuah graf berarah maupun tidak.
2.Cara Kerja
Cara kerja Algoritma dijkstra memakai strategi greedy, dimana pada setiap langkah di
pilih sisi dengan bobot terkecil yang menghubungkan sebuah simpul yang sudah terpilih dengan
simpul yang sudah terpilih dengan simpul lain yang belum terpilih.
Algoritma Dijkstra membutuhkan parameter tempat asal dan tempat tujuan. Hasil akhir
dari algoritma ini adalah jarak terpendek dari tempat asal ke tempat ujuan beserta rutenya.
contoh:
3.Penerapan Algoritma Dijkstra
(Penerapan Algoritma Dijkstra pada Jaringan Komputer)
Mencari lintasan terpendek dari router asal ke router tujuan dapat diartikan sebagai
menentukan lintasan terpendek dari simpul asal ke simpul tujuan di dalam graf yang
merepresentasikan jaringan komputer tersebut. Algoritma Dijkstra adalah algoritma yang
banyak digunakan untuk mencari lintasan terpendek.
b. Algoritma Warshall
Algoritma floyd-warshall adalah satu varian dari pemrograman dinamis,yaitu dengan
memandang solusi yang akan diperoleh sebagai suatu keputusan yang saling terkait. Sehingga
solusi solusi tersebut terbentuk dari solusi yang berasal dari tahap seblumnya.Algoritma
warshall ini berbeda dengan algoritma greedy.karena algoritma greedy tidak diperhatikan
konsekuensi yang akan terjadi seandainya kita memilih suatu keputusan pada suatu tahap.
Algoritma warshall disebut juga algoritma dinamis.
karakteristik dari algoritma dinamis ialah :
1. persoalannya dibagi atas beberapa tahap,yang setiap tahapnya diambil satu keputusan.
2. Masing-masing tahap terdiri dari sejumlah status yang saling berhubungan.
3. Hasil keputusan akan di transformasikan.
4. Ongkos tergantung dari ongkos tahapan yang telah berjalan dan ongkos pada tahap itu
sendiri.
5. Keputusan terbaik pada tahap bersifat independen.
6. Terdapat hubungan rekursif yang menyatakan bahwa keputusan terbaik dalam setiap status
pada tahap -k.
Pada algoritma ini dilakukan pendekatan ,yaitu pendekatan maju dan pendekatan mundur.
Analisisnya :
Melakukan perbandingan terlebih dahulu,yaitu pada tiap tahap antara 2 simpul hingga
perkiraan tersebut diketahui sebagai nilai optimal. Ada 2 kemungkinan yang terjadi jika kita
mencari jalur terpendek (shortest path) dari setiap i ke simpul j dan perantara simpul 1 s.d ke
k+1,
1. Jalur terpendek hanya berasal dari simpul yang berada antara 1 hingga k.
2. Ada sebagian jalur yang berasal dari simpul 1 s/d k+1 dan juga dari k+1 hingga i.
Maka dari itu rumus fungsi shortest path dengan algoritma ini ;