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 ;

basis -0

shortest path(i,j,0)=edgecost(i,j);

rekurens

shortest path (i,j,k) = min(shortestpath (i,,j,k-1),shortestpath(i,k,k-1)+shortestpath(k,j,k-1);

pengertian dari wikipedia :

Algoritma Floyd-Warshall memiliki input graf berarah dan berbobot (V,E), yang berupa daftar

titik (node/vertex V) dan daftar sisi (edge E). Jumlah bobot sisi-sisi pada sebuah jalur adalah

bobot jalur tersebut. Sisi pada E diperbolehkan memiliki bobot negatif, akan tetapi tidak

diperbolehkan bagi graf ini untuk memiliki siklus dengan bobot negatif. Algoritma ini

menghitung bobot terkecil dari semua jalur yang menghubungkan sebuah pasangan titik, dan

melakukannya sekaligus untuk semua pasangan titik. Algoritma ini berjalan dengan waktu Θ(|

V|3).

Implementasi algoritma ini dalam pseudocode: (Graf direpresentasikan sebagai matrix

keterhubungan, yang isinya ialah bobot/jarak sisi yang menghubungkan tiap pasangan titik,

dilambangkan dengan indeks baris dan kolom) (Ketiadaan sisi yang menghubungkan sebuah

pasangan dilambangkan dengan Tak-hingga)

function fw( int [1..n,1..n] graph) { // Inisialisasi var int [1..n,1..n] jarak := graph var int [1..n,1..n]

sebelum for i from 1 to n for j from 1 to n if jarak[i,j] jarak[i,k] + jarak[k,j] jarak[i,j] = jarak[i,k] +

jarak[k,j] sebelum[i,j] = sebelum[k,j] return jarak }