SIMULASI PENCARIAN JALUR TERPENDEK ANTARA DUA TEMPAT MENGGUNAKAN ALGORITMA DJIKSTRA

ABSTRAKSI

Perkembangan dalam dunia komputer begitu pesat. Hal ini menyebabkan iku berkembangnya dunia komputasi. Banyak persoalan sekarang ini dipecahkan dengan model/metode perhitungan komputasi. Salah satunya adalah dalam pencarian jalur terpendek. Pencarian jalur terpendek dapat dimodelkan dalam bentuk graf. Untuk mencari jalur terpendek dalam graf dapat dilakukan dengan beberapa algoritma, salah satunya Dijkstra.

Penelitian ini memodelkan masalah ke dalam graf dan memanfaatkan algoritma Dijkstra untuk mencari jalur terpendeknya.

Kata kunci : algoritma Dijkstra, jalur terpendek, shortest path, graph, simulasi

  1. 1. PENDAHULUAN

Teknologi komputer saat ini berkembang dengan sangat cepat. Hal ini sangatlah membantu manusia dalam mengatasi berbagai hal. Kemampuan komputer dalam melakukan perhitungan dengan cepat dan akurat sangatlah terasa manfaatnya, dimana manusia memiliki keterbatasan dalam kedua hal tersebut. Kemampuan yang dimiliki oleh komputer tersebut menyebabkan computer digunakan dalam berbagai bidang, tidak hanya yang berhubungan dengan komputer saja. Penggunaan komputer disini dikhususkan pada penyelesaian suatu masalah tertentu juga.

Salah satu masalah yang sering dihadapi adalah untuk mencapai optimalisasi. Dimana dalam melakukan suatu pekerjaan, seringkali diharapkan pekerjaan tersebut diselesaikan dengan cost seminimal mungkin. Begitu juga ketika dihadapkan pada masalah pemilihan jalur maka hasil optimal yang diharapkan adalah jalur yang dipilih/dihasilkan memakan cost yang seminimal mungkin. Cost yang mungkin dalam pemilihan jalur antara lain jarak tempuh, waktu, kemacetan.

Sering kali untuk mencapai suatu tempat atau tujuan terdapat lebih dari satu (banyak) jalur yang mungkin untuk diambil. Untuk menentukan jalur mana yang sebaiknya diambil maka diperlukan suatu perhitungan. Perhitungan diperlukan agar menghasilkan suatu jalur yang memakan cost seminimal mungkin. Ketika cost yang dihadapi adalah jarak maka perhitungan disini akan menghasilkan jalur dengan total jarak terpendek.

  1. 2. Defenisi graf

Graf G didefenisikan sebagai pasangan himpunan (V,E), ditulis dengan notasi

G = (V,E), yang dalam hal ini V adalah himpunan tidak kosong dari simpul – simpul(vertices atau node) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul (Munir,2005).

Defenisi diatas menyatakan V adalah himpunan tidak kosong, sedangkan E boleh kosong. Jadi sebuah graf harus memiliki paling tidak satu buah simpul (vertices atau node) dan boleh tidak memiliki sisi (edges atau arcs).

2.1. Jenis – jenis graf

Graf dapat dikelompokan dalam beberapa kelompok. Pengelompokan ini

dapat dilakukan berdasarkan jumlah simpul, ada tidaknya sisi ganda maupun

orientasi arah dari sisi pada graf. Berdasarkan orientasi arah pada sisi, maka graf dapat dibedakan menjadi dua yaitu graf tak-berarah dan graf berarah(Munir,2005). Graf tak berarah adalah graf yang sisi – sisinya tidak memiliki orientasi arah. Hal ini menyebabkan pada graf tak-berarah, urutan pasangan simpul yang berhubungan tidak diperhatikan. Jadi sisi (u,v) pasti sama dengan sisi (v,u).

Sebaliknya dengan graf berarah, yaitu graf yang sisi – sisinya memiliki orientasi arah, urutan pasangan simpul yang berhubungan sangat diperhatikan.

Sisi (u,v) belum tentu sama dengan sisi (v,u). Pada graf berarah, sisi (u,v) simpul u dinamakan simpul asal (initial vertex) dan simpul v dinamakan simpul terminal

(terminal vertex).

2.2. Representasi graf

Representasi graf dilakukan ketika suatu graf akan diproses oleh program komputer. Terdapat beberapa jenis representasi graf, jenis representasi yang digunakan dalam penelitian ini adalah matrik ketetanggaan. Jenis representasi graf ini merupakan jenis yang paling banyak digunakan. Dikatakan misal terdapat graf dengan n simpul,

G = (V,E), n > 1. Maka matriks ketetanggaan G adalah matriks

dwimatra yang berukuran n x n. Bila matriks tersebut dinamakan A = [aij], maka aij = 1 jika simpul i dan j bertetangga, sebaliknya aij = 0 jika simpul i dan j tidak bertetangga (Munir,2005). Pada graf berbobot maka aij = nilai dari bobot sisi yang menghubungkan simpul i dan j, jika tidak terdapat sisi yang menghubungkan

simpul i dan j maka aij = ∞.

3. Algoritma Dijkstra

Algoritma Dijkstra adalah sebuah algoritma rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot – bobot sisi (edge weights) yang bernilai tidak negatif. 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 (www.wikipedia.org). Algoritma ini ditemukan oleh Edger W. Dijkstra. Pada naskah aslinya, algoritma ini digunakan untuk mencari lintasan terpendek pada graf berarah, algoritma ini akan selalu bernilai benar bila

diterapkan pada graf tak berarah.

Menurut Jong Jek Siang dalam buku “Matematika Diskrit dan Aplikasinya pada Ilmu Komputer” (2006), misalkan :

V(G) = {v1,v2,…,vn}.

L = Himpunan titik – titik V(G) yang sudah terpilih dalam jalur Path terpendek.

D(j) = Jumlah bobot path terkecil dari v1 ke vj.

W(i,j) = Bobot garis dari titik vi ke titik vj.

W*(1,j) = Jumlah bobot path terkecil dari v1 ke vj

maka secara formal algoritma Dijkstra untuk mencari path terpendek adalah

sebagai berikut :

1. L = {};

V = {v2, v3,…, vn};

2. Untuk I = 2,…,n, lakukan D(i) = W(1,i)

3. Selama Vn ∉ L lakukan :

a. Pilih titik vk V-L dengan D(k) terkecil.

L = L {vk}

b. Untuk setiap vj V-L lakukan:

Jika D(j) > D(k) + W(k+j) maka ganti D(j)

dengan D(k) + W(k,j)

4. Untuk setiap vj V, w*(1,j) = D(j);

Berdasarkan algoritma diatas maka path terpendek dari titik v1 ke vn adalah

melalui titik – titik dalam L secara berurutan, dan jumlah bobot path terkecilnya adalah D(n).

  1. 3. Hasil

Algoritma diatas diterapkan untuk menyelesaikan persoalan sebagai berikut :

Rute yang dicari adalah dari titik a menuku ke titik f. Hasil perhitungan manual menghasilkan :

f [12] à e [9] à c[5] à b[3] à a[0]

dengan total jarak = 12.

Dengan soal yang sama digunakan aplikasi yang dibuat dalam penelitian ini. Berikut tampilan aplikasi :

Aplikasi telah dapat melakukan perhitungan secara tepat sesuai dengan perhitungan maual. Rute hasil dari perhitungan ditandai dengan garis berwarna merah.

  1. 4. Kesimpulan

Kesimpulan dari penelitian ini sebagai berikut :

  1. Algoritma djikstra dapat digunakan untuk menyelesaikan persoalan pencarian rute terpendek pada sebuah graf.
  2. Kelemahan algoritma ini adalah semakin banyak titik akan semakin memakan waktu proses.
  3. Jumlah titik menentukan tingkat efektifitas dari algoritma djikstra.

DAFTAR PUSTAKA

Suyanto, ST, M.Sc, 2007,”ARTIFICIAL INTELLIGENCE Searching, Reasoning,Planning dan Learning”, INFORMATIKA,BANDUNG, Indonesia

Siang, J.J., Drs, M.Sc, 2006,”MATEMATIKA DISKRIT dan APLIKASINYA pada ILMU KOMMPUTER”,ANDI, Yogyakarta, Indonesia

Munir, R., 2005,”MATEMATIKA DISKRET”, INFORMATIKA, BANDUNG, Indonesia

“Algoritma Dijkstra”, http://id.wikipedia.org/wiki/Algoritma_Dijkstra

waktu akses : 1 Desember 2007, 9.40 WIB

“Algoritma Greedy untuk Menentukan Lintasan Terpendek” oleh Irvan Prama

Defindal, Boyke Ariesanda, Christoforus,

http://www.informatika.org/~rinaldi/Stmik/MakalahStimik16.pdf

waktu akses : 1 Desember 2007, 10.57 WIB

2 Balasan ke SIMULASI PENCARIAN JALUR TERPENDEK ANTARA DUA TEMPAT MENGGUNAKAN ALGORITMA DJIKSTRA

  1. Araditiya mengatakan:

    Terima kasih sharingnya.

  2. defindal mengatakan:

    wah, makalah lama ternyata di refer juga..🙂

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: