Kamis, 31 Maret 2011

MAKALAH GRAF DENGAN ALGORITMA DJIKSTRA

A. Latar belakang
Makalah ini membahas tentang persoalan lintasan terpendek suatu graf dengan algoritma dijikstra. 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 solusi penyelesaian yang paling efektif 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. Tetapi pada kesempatan ini kita hanya akan membahas tentang algoritma dijkstra.

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).



B. Pembatasan Masalah
Melihat dari latar belakang masalah serta memahami pembahasannya maka penulis dapat memberikan batasan-batasan pada :

1. Persoalan lintasan terpendek pada Graf..
2. Algoritma Djikstra dalam pseudo-code.
3. Analisa Algoritma Djikstra.

C. Rumusan Masalah

Masalah yang dibahas dalam penulisan makalah ini adalah :

1. Bagaimana cara untuk mengetahui prsoalan lintasan terpendek pada Graf?
2. Bagaimana cara untuk mengetahui Algoritma Djikstra dalam pseudo-code?
3. Bagaimana cara menganalisa Algoritma Djikstra?


D. Tujuan Penulisan
Tujuan daripada penulisan makalah ini adalah :
1. Mengetahui Persoalan lintasan terpendek pada Graf.
2. Mengetahui Algoritma Djikstra dalam pseudo-code.
3. Mengetahui Analisa Algoritma Djikstra .

E. Manfaat Penulisan
Hasil dari penulisan ini diharapkan dapat memberikan manfaat kepada semua pihak, khususnya kepada mahasiswa untuk menambah pengetahuan dan wawasan dalam Persoalan lintasan terpendek pada Graf dengan menggunakan Algoritma Djikstra . Manfaat lain dari penulisan makalah ini adalah dengan adanya penulisan makalah ini diharapkan dapat dijadikan acuan didalam membuat sebuah Graf dengan mmenggunakan Algoritma Djikstra.

F. Metode Pengumpulan Data
Data penulisan makalah ini diperoleh dengan metode survey, Selain itu, tim penulis juga memperoleh data dari internet.


PENDAHULUAN

Permasalah optimasi merupakan permasalahan yang sering sekali kita temui dalam
kehidupan sehari-hari. Hal ini tidak lepas dari sifat dasar manusia yang selalu ingin mendapat keuntungan semaksimum mungkin dan memperoleh kerugian seminimum mungkin. Jika kita membicarakan permasalahan mengenai rute atau jalur yang menghubungkan tempat-tempat tertentu maka kita sering menggambarkanya dengan bulatan untuk memvisualisasikan tempat dan garis untuk jalan / rute. Representasi semacam ini merupakan suatu representasi dari graf.
Graf adalah himpunan simpul yang dihubungkan dengan suatu garis dimana garis tersebut menghubungkan dengan tepat ke 2 simpul sehingga simpul-simpul ini saling berhubungan. Dalam kehidupan sehari-hari banyak sekali persoalan yang di implementasikan dengan graf. Bidang-bidang yang menggunakan penerapan graf antara lain Switching network, Coding theory, Electrical analysis, Operation research, aljabar, computer science, dan kimia.
Banyak sekali aplikasi yang mengunakan graf sebagai alat untuk merepresentasikan atau memodelkan persoalan sehingga persoalan itu dapat diselesaikan dengan baik. Aplikasiaplikasi tersebut misalnya menentukan lintasan terpendek (the shortest path problem), traveling salesman problem, chinese postman problem, graf colouring, Making a road system one-way, rangking the participants in a tournament, dan masih banyak lagi. Dalam kesempatan ini kami mencoba mengulas tentang persoalan menentukan lintasan terpendek (The Shortest Path Problem).
Menurut teori graf, persoalan lintasan terpendek adalah suatu persoalan untuk mencari
lintasan antara dua buah simpul pada graf berbobot yang memiliki gabungan nilai jumlah
bobot pada sisi graf yang dilalui dengan jumlah yang paling minimum. Persoalan lintasan
terpendek ini banyak sekali dijumpai di kehidupan sehari-hari. Aplikasi yang paling sering ditemui adalah pada bidang transportasi, seperti pada pencarian rute terbaik untuk menempuh dua kota.

Persoalan Lintasan Terpendek Pada Graf
Menurut teori graf, persoalan lintasan terpendek adalah suatu persoalan untuk mencari lintasan antara dua buah simpul pada graf berbobot yang memiliki gabungan nilai jumlah bobot pada sisi graf yang dilalui dengan jumlah yang paling minimum atau dapat dinyatakan juga sebagai berikut : diberikan sebuah graf berbobot (dengan himpunan simpul V, himpunan sisi E, dan fungsi bobot bernilai bilangan riil yang dapat ditulis dengan f : E → R), dan diberikan elemen v dari V, sehingga dapat dicari sebuah lintasan P dari v ke setiap v' dari V, sehingga
Ʃ f(p)
pϵP adalah nilai minimum dari semua lintasan yang menghubungkan v ke v'.

Persoalan lintasan terpendek merupakan salah satu persoalan optimasi yeng menggunakan graf berbobot, dimana bobot pada setiap sisi graf tersebut dapat kita gunakan untuk menyatakan jarak kota, waktu pengiriman pesan, ongkos pembangunan, dan sebagainya.

• Aplikasi dari Persoalan lintasan terpendek pada Graf
Ada beberapa macam persoalan lintasan terpendek, antara lain :
1. Lintasan terpendek antara dua buah simpul tertentu
2. Lintasan terpendek antara semua pasangan simpul
3. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain
4. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu

Aplikasi persoalan penentuan lintasan terpendek ini banyak sekali kita jumpai dalam
kehidupan sehari-hari :
a. Menentukan rute / jalur terbaik yang harus ditempuh dari suatu kota menuju ke kota
yang lain
b. Menentukan jalur komunikasi 2 buah terminal komputer
c. Menentukan jalur penerbangan dunia yag paing efektif untuk di lakukan.


ALGORITMA DIJKSTRA

Edsger Wybe Dijkstra, menemukan suatu algoritma untuk mencari lintasan terpendek
pada suatu graf. Algoritma Dijkstra pada awalnya diterapkan pada graf berarah, tetapi
ternyata algoritma ini juga benar untuk algoritma graf tak-berarah. Algoritma ini menggunakan prinsip greedy yang digunakan untuk menyatakan bahwa pada setiap langkah kita memilih sisi yang berbobot minimum dan memasukannya ke dalam himpunan solusi.
Akan tetapi bobot dari graf tersebut harus bernilai bilangan positif (bobot >=0). 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. Algoritma dijkstra dimulai dari sebuah simpul asal dan dalam setiap iterasinya menambahkan sebuah verteks lain ke lintasan terpendek pohon merentang. Verteks ini
merupakan titik terdekat ke akar namun masih diluar bagian pohon.
Properti Algoritma Djikstra :
1. Matriks Ketetangga M[mij]
mij = bobot sisi (i,j) ; pada graf tak berarah mij = mji
mii = 0
mij = , jika tidak a ꝏ da sisi dari simpul i ke simpul j
2. Larik S = [si] yang dalam hal ini,
si = 1, jika simpul i termasuk ke dalam lintasan terpendek
si = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek
3. Larik/tabel D = [di] yang dalam hal ini,
di = panjang lintasan dari simpul awal s ke simpul I

 Algoritma djikstra dalam pseudo-code :
procedure Dijkstra (input m: matriks, a:simpul awal)
{mencari lintasan terpendek dari simpul awal a ke semua simpul lainya
Masukan : matriks ketetanggaa (m) dari graf berbobot G dan
simpul awal a
Keluaran: lintasan terpendek dari a ke semua simpul lainnya}

• Deklarasi
s1,s2,...,sn : interger {larik interger}
d1,d2,...,dn : interger {larik interger}
i : interger



• Algoritma
{Langkah 0 (inisialisasi) : }
for i ← 1 to n do
si ← 0
di ← mai
endfor
{Langkah 1: }
sa ← 1 {karena simpul a adalah simpul asal lintasan terpendek, jadi terpilih dalam lintasan terpendek}
da ← ꝏ {tidak ada lintasan terpendek dari simpul a ke a}
{Langkah 2,3,...,n1:}
for i ← 2 to n1 do
Cari j sedemikian sehingga sj = 0 dan dj = min {d1,d2,...,dn}
Sj ← 1 {simpul j sudah terpilih ke dalam lintasan terpendek}
perbarui di, untuk i = 1,2,3,...,n
dengan : di (baru) = min {di(lama), dj + mji}
endfor
Analisa Algoritma Dijkstra

Algoritma ini mirip dengan algoritma Prim untuk mencari MST, yaitu pada tiap iterasi
memeriksa sisi-sisiyang menghubungkan subset verteks W dan subset verteks (V-W) dan
memindahkan verteks w dari (VW) ke W yang memenuhi kriteria tertentu. Perbedaannya
terletak pada kriteria itu sendiri. Dalam algoritma Dijkstra, yang dicari adalah sisi yang
menghubungkan ke suatu verteks di (V-W) sehingga jarak dari verteks asal Vs ke verteks
tersebut adalah minimal.
Dalam implementasinya penghitungan jarak dari verteks asal vs disederhanakan dengan
menambahkan field minpath pada setiap verteks. Field-field minpath ini diinisialisasi sesuai dengan adjacency-nya dengan vs, kemudian dalam setiap iterasi di-update bersamaan masuknya w dalam W. Field minpath ini menunjukkan jarak dari vs ke verteks yang bersangkutan terpendek yang diketahui hingga saat itu. Jadi pada verteks dalam W, minpath sudah menunjukkan jarak terpendek dari Vs untuk mencapai verteks yang bersangkutan, sementara pada (V-W) masih perlu di-update pada setiap iterasi dalam mendapatkan verteks.
w seperti diterangkan di atas. Yaitu, setiap mendapatkan w maka update minpath setiap
adjacent verteks x dari w di (V-W) sisa dengan:
minimum (minpath dari x , total minpath w + panjang sisi yang bersangkutan). Agar dapat berlaku umum maka di awal algoritma seluruh minpath diinisialisasi
dengan +∞.

Demikian halnya pencarian w itu sendiri disederhanakan menjadi pencarian node di (VW) dengan minpath terkecil. Selengkapnya algoritma Dijkstra adalah sebagai berikut :

1. Inisialisasi
W berisi mula-mula hanya vs, field minpath tiap verteks v dengan Weight[vs, v], jika
ada sisi tersebut, atau, +∞ jika tidak ada.
2. Lalu, dalam iterasi lakukan hingga (V-W) tak tersisa (atau dalam versi lain: jika ve
ditemukan) dari field minpath tiap verteks cari verteks w dalam (V-W) yang memiliki
minpath terkecil yang bukan tak hingga. Jika ada w maka masukkan w dalam W.
Update minpath pada tiap verteks t adjacent dari w dan berada dalam (VW) dengan:
minimum (minpath[t] , minpath[w] + weight [w, t]).

Verteks-verteks dalam W dapat dibedakan dari verteks dalam (V-W) dengan suatu field
yang berfungsi sebagai flag atau dengan struktur linked-list. Informasi lintasan dapat
diketahui dengan pencatatan predesesor dari setiap verteks yang dilakukan pada saat update harga minpath tersebut (fungsi minimum). Jika minpath[t] di-update dengan (minpath[w] + Weight [w, t]) maka predesesor dari t adalah w. Pada tahap inisialisasi predesesor setiap verteks diisi oleh vs.
Algoritma Dijkstra membuat label yang menunjukkan simpul-simpul. Label-label ini
melambangkan jarak dari simpul asal ke suatu simpul lain. Dalam graf, terdapat dua macam label, sementara dan permanen. Label sementara diberikan untuk simpul-simpul yang belum dicapai. Nilai yang diberikan untuk label sementara ini dapat beragam. Label permanen diberikan untuk simpul-simpul yang sudah dicapai dan jarak ke simpul asal diketahui. Nilai yang diberikan untuk label ini ialah jarak dari simpul ke simpul asal. Suatu simpul pasti memiliki label permanen atau label sementara. Tetapi tidak keduanya.

Algoritma dimulai dengan menginisialisasi simpul manapun di dalam graf (misalkan
simpul A) dengan label permanen bernilai 0 dan simpul-simpul sisanya dengan label
sementara bernilai 0. Algoritma ini kemudian memilih nilai sisi terendah yang menghubungkan simpul dengan label permanen (dalam hal ini simpul A) ke sebuah simpul lain yang berlabel sementara (misalkan simpul V). Kemudian label simpul V di-update dari label sementara menjadi label permanen. Nilai simpul V merupakan penjumlahan nilai sisi dan nilai simpul A.
Langkah selanjutnya ialah menemukan nilai sisi terendah dari simpul dengan label sementara, baik simpul A maupun simpul B (misalkan simpul E). Ubah label simpul E menjadi permanen, dan ukur jarak ke simpul A. Lamanya waktu untuk menjalankan Algoritma Dijkstra's pada suatu graf dengan Y (himpunan sisi) dan Z (himpunan simpul) dapat dinyatakan sebagai fungsi Y dan Z menggunakan notasi Big-O. Waktu yang dibutuhkan algoritma Dijkstra untuk bekerja ialah sebesar O(V*log V + Y). Implementasi paling sederhana dari algoritma Dijkstra ialah penyimpanan simpul dari suatu himpunan ke dalam suatu array atau list berkait.
CONTOH ILUSTRASI GRAF


KETERANGAN:
A : KAMPUS J3
B : MALL METROPOLITAN
C : KAMPUS J1
D : McD. PANGKALAN JATI
E : HALIM
F : KAMPUS UKI
G : CAWANG
H : PGC
I : LAMPU MERAH CIJANTUNG
J : MALL CIJANTUNG
K : LAMPU MERAH CIRACAS
L : MABES TNI AD
M : KAMPUS E
N : KAMPUS MARGONDA
O : KAMPUS UI
P : TMP KALIBATA
Q : MALL TAMINI
R : PASAR PONDOK GEDE
S : KAMPUS UNKRIS
T : PEKAYON
V : KAMPUS KEMANG PRATAMA
W : BEKASI SQUARE

Penyelesaian jalur terpendek untuk graf diatas :

Maka Total jarak yang ditempuh dari kampus J3 sampai ke kampus MARGONDA DEPOK adalah = 26 km dengan jalur (A-V-T-R-Q-I-J-L-M-N).


KESIMPULAN

1. Persoalan mencari lintasan terpendek dari setiap graf berbobot, merupakan masalah optimasi.
2. Algoritma Dijkstra merupakan salah satu algoritma yang digunakan untuk memecahkan permasalahan lintasan terpendek yang terdapat pada suatu graf.
3. Algoritma ini digunakan pada graf berbobot dengan syarat bobot dari masing-masing sisi haruslah bernilai positif (>=0).
4. Salah satu implementasi dari algoritma Dijkstra ialah penyimpanan simpul dari suatu himpunan ke dalam suatu array atau list berkait (linked list).
5. Dalam mencari lintasan terpendek, algoritma yang paling banyak digunakan orang
ialah algoritma Dijkstra, karena kerjanya efisien dan tidak membutuhkan waktu yang banyak. Tetapi Algoritma Dijkstra yang menerapkan prinsip greedy tidak selalu berhasil memberikan solusi optimum untuk kasus penentuan lintasan terpendek (single pair shortest path).


SARAN :
Menurut kami, Algoritma Dijkstra merupakan salah satu algoritma yang digunakan untuk memecahkan permasalahan lintasan terpendek yang terdapat pada suatu graf untuk mencari lintasan terpendek pada Graf, Tetapi Algoritma Dijkstra yang menerapkan prinsip greedy tidak selalu berhasil memberikan solusi optimum untuk kasus penentuan lintasan terpendek (single pair shortest path).

DAFATAR PUSTAKA

http://www.freewebs.com/infoitn/Materi/graf/Presentasi/Makalah%20Dijkstra.pdf

3 komentar:

  1. Mantaap gan postingannya :)
    Referensi algoritma Djikstra: http://sunaryoo.wordpress.com/unduhan/

    BalasHapus