Algoritma Dijkstra

Algoritma Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.

Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.

Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G.

Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua tepi disebut E.

Bobot (weights) dari semua sisi dihitung dengan fungsi

w: E → [0, ∞)

jadi w(u,v) adalah jarak tak-negatif dari vertex u ke vertex v.

Ongkos (cost) dari sebuah sisi dapat dianggap sebagai jarak antara dua vertex, yaitu jumlah jarak semua sisi dalam jalur tersebut. Untuk sepasang vertex s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t

Penyelesaian Masalah Lintasan Terpendek (Shortest Path) Dengan Menggunakan Algoritma Johnson

graph adalah salah satu cabang dari ilmu matematika yang sangat penting dan banyak sekali aplikasinya. Salah satunya adalah penyelesaian masalah lintasan terpendek. Ada beberapa metode yang sudah ada dan sering digunakan untuk menyelesaikan masalah lintasan terpendek, misalnya Algoritma Dijkstra, Algoritma Bellman Ford dan Algoritma Floyd-Warshall. Selain menggunakan metode-metode tersebut, ada metode lain yang dapat digunakan untuk menyelesaikan masalah lintasan terpendek yaitu Algoritma Johnson.
Dalam skripsi ini dibahas tentang penyelesaian masalah lintasan terpendek (shortest path) dengan menggunakan Algoritma Johnson. Langkah awal penyelesaian Algoritma Johnson adalah mengkonstruksi digraph baru dengan menambahkan titik baru pada digraph dan memberi bobot sisi yang keluar dari titik baru tersebut dengan 0. Langkah selanjutnya adalah mencari lintasan terpendek dari titik baru ke semua titik lain. Lintasan terpendek tersebut digunakan untuk mengubah bobot semua sisi pada digraph baru agar bobot semua sisi bernilai positif. Setelah itu mencari lintasan terpendek dari tiap titik ke semua titik lain dan mengubah hasilnya dengan menggunakan lintasan terpendek dari titik baru ke semua titik lain. Hasil dari perhitungan ini berupa matriks. Dari matriks ini dapat diketahui panjang lintasan terpendek dari tiap titik ke semua titik lain. Untuk menghitung lintasan terpendek dari titik baru ke semua titik lain yang berguna untuk mengubah semua bobot menjadi positif digunakan Algoritma Bellman-Ford. Untuk menghitung lintasan terpendek dari tiap titik ke semua titik lain yang semua bobot sisinya sudah bernilai positif digunakan Algoritma Dijkstra.
Kelebihan Algoritma Johnson ini adalah dapat digunakan untuk digraph yang berbobot negatif dan untuk menyelesaikan masalah lintasan terpendek dari tiap titik ke semua titik lain.Untuk memeriksa kebenaran perhitungan dari Algoritma Johnson dapat digunakan Algoritma Floyd-Warshall. Dari proses perhitungan diperoleh hasil yang sama antara penyelesaian masalah lintasan terpendek dengan menggunakan Algoritma Johnson dan Algoritma Floyd-Warshall. Untuk memeriksa perhitungan secara manual, dalam skripsi ini juga digunakan program bantu GIDEN.
. ALGORITMA DIJKSTRA  digunakan untuk mencari rute terpendek……

berikut ini contohnya ::

Graph G dengan matrik berhubungan langsung sebagai berikut ::

	A	B	C	D	E	F	G
A	0	60	70	∞	∞	∞	∞
B	60	0	50	50	20	∞	∞
C	70	50	∞	40	∞	70	∞
D	∞	50	40	0	60	50	∞
E	∞	20	∞	60	0	30	40
F	∞	∞	70	50	30	0	50
G	∞	∞	∞	∞	40	50	0

GAMBAR GRAPHNYA SEPERTI INI ::

untuk bobotnya dapat dilihat pada tabel yang sebenarnya sebuah “matrik berhubungan langsung” di samping..

PENYELESAIANNYA ::

Titik Vi	A	B	C	D	E	F	G
x (Vi)	∞	∞	∞	∞	∞	∞	0
T	A	B	C	D	E	F	G
Titik Vi	A	B	C	D	E	F	G
x (Vi)	∞	∞	∞	∞	40	50	0
T	A	B	C	D	E	F	-
Titik Vi	A	B	C	D	E	F	G
x (Vi)	∞	60	∞	100	40	50	0
T	A	B	C	D	-	F	-
Titik Vi	A	B	C	D	E	F	G
x (Vi)	∞	60	120	100	40	50	0
T	A	B	C	D	-	-	-
Titik Vi	A	B	C	D	E	F	G
x (Vi)	120	60	110	100	40	50	0
T	A	-	C	D	-	-	-
Titik Vi	A	B	C	D	E	F	G
x (Vi)	120	60	110	100	40	50	0
T	A	-	C	-	-	-	-
Titik Vi	A	B	C	D	E	F	G
x (Vi)	120	60	110	100	40	50	0
T	A	-	-	-	-	-	-
Titik Vi	A	B	C	D	E	F	G
x (Vi)	120	60	110	100	40	50	0
T	-	-	-	-	-	-	-

Jadi secara umum cara untuk menyelesaikan algoritma dijkstra adalah ::

Input :: Graph bobot G dengan s,t elemen V(G)

Step 1 :: Label titik dengan λ(s)=0 dan untuk setiap titik v di G selain s, label titik v dengan λ(v)=∞ (dalam praktek ∞ diganti dengan bilangan yang “sangat besar” atau diibaratkan sebagai bilangan yang sangat besar). Tulis T = V(G).

Step 2 :: Misalkan u ε T denga λ(u) minimum

Step 3 :: Jika u = t, STOP, dan beri pesan: “Panjang lintasan terpendek dari s ke t adalah λ(t)”.

Step 4 :: untuk setiap sisi e = uv, v ε T, diganti label v dengan λ(v)= minimum {λ(v),λ(u)+W(e)}.

Step 5 :: Tulis T = T – {u}, dan kembali ke step 2………

keterangan simbol ::

λ = Lamda

ε = elemen

Definisi Strategi Algoritma Floyd Warshall

Hal yang membedakan pencarian solusi menggunakan pemrograman dinamis (Warshall) dengan algoritma greedy adalah, bahwa keputusan yang diambil pada tiap tahap pada algoritma greedy hanya berdasarkan pada informasi yang terbatas, sehingga hanya nilai optimum yang diperoleh pada saat itu. Jadi pada algoritma greedy, kita tidak memikirkan konsekuensi yang akan terjadi seandainya kita memilih suatu keputusan pada suatu tahap. Dalam beberapa kasus, Algoritma Greedy gagal memberikan solusi terbaik karena kelemahan yang dimilikinya tadi. Di sinilah peran pemrograman dinamis yang mencoba untuk memberikan solusi yang memiliki pemikiran terhadap konsekuensi yang ditimbulkan dari pengambilan keputusan pada suatu tahap.

Pemrograman dinamis mampu :

• Mengurangi pengenumerasian (Pendaftaran) keputusan yang tidak mengarah ke solusi.

• Prinsip yang dipegang oleh pemrograman dinamis adalah prinsip optimalitas, yaitu jika solusi total optimal, maka bagian solusi sampai suatu tahap (misalnya tahap ke-i) juga optimal.


Analisis Algoritma Floyd-Warshall

Algoritma Floyd-Warshall membandingkan semua kemungkinan lintasan pada graf untuk setiap sisi dari semua simpul. Hal tersebut bisa terjadi karena adanya perkiraan pengambilkan keputusan (pemilihan jalur terpendek) pada setiap tahap antara dua simpul, hingga perkiraan tersebut diketahui sebagai nilai optimal. Misalkan terdapat suatu graf G dengan simpul-simpul V yang masing-masing bernomor 1 s.d. N (sebanyak N buah). Misalkan pula terdapat suatu fungsi shortestPath(i, j, k) yang mengembalikan kemungkinan jalur terpendek dari i ke j dengan hanya memanfaatkan simpul 1 s.d. k sebagai titik perantara. Tujuan akhir penggunaan fungsi ini adalah untuk mencari jalur terpendek dari setiap simpul i ke simpul j dengan perantara simpul 1 s.d. k+1.

Ada dua kemungkinan yang terjadi:

• Jalur terpendek yang sebenarnya hanya berasal darisimpul-simpul yang berada antara 1 hingga k.
• Ada sebagian jalur yang berasal dari simpul-simpul i s.d. k+1, dan juga dari k+1 hingga j.

Contoh Kasus Algoritma Floyd-Warshall

Ada beberapa jalur antara A dan E:
Path 1 : A -> B -> E 20
Path 2 : A -> D -> E 25
Path 3 : A -> B -> D -> E 35
Path 4 : A -> D -> B -> E 20




Ada beberapa hal yang harus dilihat
di grafik tersebut :

• Ada bisa lebih dari satu rute antara dua node.
• Jumlah node dalam rute tersebut tidak penting (Jalur 4 memiliki 4 node tetapi lebih pendek dari Jalur 2, yang memiliki 3 node).
• Ada bisa lebih dari satu jalur panjang minimal.






Pada algoritma ini diperhatikan agar hasil akhir adalah se-optimum mungkin. Pada jarak antar kota di atas, dari kota A untuk menuju kota F terdapat beberapa jalur, dapat melalui kota B terlebih dahulu, kota E, atau kota C. Pada algoritma ini dipilih jalur melalui kota C kemudian ke kota F sehingga jarak tempuh total adalah 72 km. Berbeda jika kita memilih kota B atau E terlebih dahulu, karena akan menghasilkan jarak tempuh yang lebih panjang.


Kesimpulan

• Algoritma Floyd-Warshall yang menerapkan pemrograman dinamis lebih menjamin keberhasilan penemuan solusi optimum untuk kasus penentuan lintasan terpendek (single pair shortest path).
• Prinsip yang dipegang oleh pemrograman dinamis adalah prinsip optimalitas, yaitu jika solusi total optimal, maka bagian solusi sampai suatu tahap (misalnya tahap ke-i) juga optimal.