Makalah algoritma djikstra

KATA PENGANTAR

             Dengan nama Allah yang maha pengasih lagi maha penyayang, Segala puji bagi Allah SWT yang telah memberikan rahmat serta karunia-Nya kepada kami sehingga kami berhasil menyelesaikan Makalah yang berjudul “Algoritma dijkstra”
            Pembuatan makalah ini bertujuan untuk memenuhi tugas mata kuliah Struktur data. Adapun yang kami bahas dalam makalah ini adalah algoritma dijakstra.

            Kami menyadari bahwa makalah ini masih jauh dari sempurna, oleh karena itu kritik dan saran dari semua pihak yang bersifat membangun selalu kami harapkan demi kesempurnaan makalah ini.
            Akhir kata, kami sampaikan terima kasih kepada semua pihak yang telah berperan serta dalam penyusunan makalah ini dari awal sampai akhir. Semoga Allah SWT senantiasa meridhai segala usaha kita.

Amin.

Bekasi, 25 Mei 2016


Kelompok 2

USNI

DAFTAR ISI

KATA PENGANTAR............................................................................................ i

DAFTAR ISI............................................................................................................ ii

BAB I PENDAHULUAN....................................................................................... 1

Latar Belakang ..........................................................................................................  1

Rumusan masalah....................................................................................................... 1

Tujuan dan manfaat penelitian................................................................................... 2

BAB II ......................................................................................................................  3

Teori dasar graf.......................................................................................................... 3

Graf berbobot............................................................................................................. 4

Lintasan terpendek..................................................................................................... 4

Algoritma dijkstra...................................................................................................... 4

BAB III..................................................................................................................... 10

Kesimpulan................................................................................................................ 10

DAFTAR PUSTAKA............................................................................................. 11

     

      BAB I

LATAR BELAKANG

Kita mengetahui bahwa untuk menuju ke suatu kota tujuan dapat ditempuh melalui

beberapa lintasan. Dalam hal ini, kita akan menentukan kota-kota atau jalan manakah

yang harus dilalui sehingga kita dapat mencari tempat tujuan dengan jarak terpendek.

Dengan demikian lintasan terpendek dapat diartikan sebagai bobot minimal dari suatu

lintasan, yaitu jumlah bobot dari seluruh busur yang membentuk lintasan. Dalam menentukan

lintasan terpendek dapat diperoleh dengan beberapa algoritma matematika, antara lain

algoritma Dijkstra, algoritma Floyd-Warshall dan algoritma Bellman-Ford.

Algoritma yang akan di pakai dalam sistem ini adalah algoritma Dijkstra. Algoritma ini

bertujuan untuk menemukan lintasan terpendek berdasarkan bobot terkecil dari satu titik

ke titik lainnya. Misalkan titik mengambarkan kota, garis menggambarkan jalan dan bobot

menggambarkan jarak, maka algoritma Dijkstra melakukan kalkulasi terhadap semua

kemungkinan bobot terkecil dari setiap titik. Dengan kata lain algoritma ini menghitung

lintasan berdasar jarak terpendek yang di tempuh di tiap-tiap kota.

1.1 Rumusan Masalah

Berdasarkan kondisi yang dijelaskan di atas, maka terdapat beberapa rumusan masalah

yang akan dijawab dalam penelitian ini

Ø  Bagaimana menentukan lintasan terpendek antar kota karena terdapat jalan yang

bercabang-cabang.

Ø  Bagaimana merancang dan menerapkan algoritma Dijkstra untuk melakukan kalkulasi

terhadap semua kemungkinan bobot terkecil dari setiap titik.

1.2 Tujuan Penelitian

Penelitian ini bertujuan antara lain:

1. Memberikan solusi dalam pemilihan lintasan terpendek pada jalan darat antara kotakota di sumatera bagian selatan meliputi provinsi Jambi, Sumatera Selatan, Bengkulu dan Lampung.

2. Mempercepat dalam mencari solusi lintasan terpendek pada jalan darat antara kotakota di sumatera bagian selatan.

3. Memperoleh hasil yang akurat dan tepat sesuai dengan keadaan di lapangan.

1.3 Manfaat Penelitian

Dengan menerapkan alogaritma dijkstra untuk mencari lintasan terdekat dapat membantu para pengguna jalan, traveling salesman, perusahaan yang bergerak dibidang pariwisata dan angkutan antar provinsi, instansi pemerintah dan lain sebagainya terutama bagi yang membutuhkan informasi tentang lintasan terdekat.

BAB II

KAJIAN TEORI

2.1 Teori Dasar Graf

Graf didefinisikan 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 [1]. Simpul pada graf dinomori dengan huruf, seperti a, b, c...dst, dengan bilangan asli 1, 2, 3...dst, atau gabungan keduanya. Sedangkan sisi yang menghubungkan simpul u dengan simpul v dinyatakan dengan pasangan (u, v) atau dinyatakan dengan lambang e1, e2....en dengan kata lain, jika e adalah sisi yang menghubungkan simpul u dengan simpul v, maka e dapat ditulis sebagai e = (u, v). Secara geometri graf digambarkan sebagai sekumpulan noktah (simpul) di dalam bidang dwimatra yang dihubungkan dengan sekumpulan garis (sisi)

                      Gambar 1. (G1) graf sederhana, (G2) multigraf, dan (G3) multigraf

Gambar di atas memperlihatkan tiga buah graf, G1, G2 dan G3 .

 G1 adalah graf dengan himpunan simpul V dan himpunan sisi E adalah:

V = {1, 2, 3, 4}

E = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)}

G2 adalah graf dengan himpunan simpul V dan himpunan sisi E adalah:

V = {1, 2, 3, 4}

E = {(1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4)}

   = {e1, e2, e3, e4, e5, e6, e7}

G3adalah graf dengan himpunan simpul V dan himpunan sisi E adalah:

V = {1, 2, 3, 4} E = {(1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3)}

   = {e1, e2, e3, e4, e5, e6, e7, e8}                    

Pada G2, sisi e3 = (1, 3) dan sisi e4= (1, 3) dinamakan sisi-ganda (multiple edges atau parallel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3. Pada G3 , sisi e8 = (3, 3) dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama.

2.2 Graf Berbobot (Weighted Graph)           

Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot) [1]. Bobot pada tiap sisi dapat berbeda-beda bergantung pada masalah yang dimodelkan dengan graf. Bobot dapat menyatakan jarak antara dua buah kota, biaya perjalanan antara dua buah kota, waktu tempuh pesan (message) dari sebuah simpul komunikasi ke simpul komunikasi lain (dalam jaringan komputer), ongkos produksi, dan sebagainya.

2.3 Lintasan Terpendek

Persoalan mencari lintasan terpendek di dalam graf merupakan salah satu persoalan optimasi. Graf yang digunakan dalam pencarian lintasan terpendek adalah graf berbobot (weighted graph), yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Bobot pada sisi graf dapat menyatakan jarak antar kota, waktu pengiriman pesan, ongkos pembangunan, dan sebagainya. Asumsi yang kita gunakan di sini adalah bahwa semua bobot bernilai positif. Kata terpendek berbeda-beda maknanya bergantung pada tipikal persoalan yang akan diselesaikan. Namun, secara umum terpendek berarti meminimisasi bobot pada suatu lintasan dalam graf [1]

2.4 Algoritma Dijkstra

Saat ini sudah banyak algoritma yang bisa digunakan untuk menemukan pencarian rute terpendek, dan tidak bisa di pungkiri Djikstra masih menjadi salah satu yang populer dari sekian banyak algoritma tersebut..

Edsger Dijkstra

Algortima ini ditemukan oleh Edsger W. Dikstra dan di publikasi pada tahun 1959 pada sebuah jurnal Numerische Mathematik yang berjudul “A Note on Two Problems in Connexion with Graphs“[1]. Algoritma ini sering digambarkan sebagai algoritma greedy (tamak). Sebagai contoh, ada pada buku Algorithmics(Brassard and Bratley [1988, pp. 87-92])

Djikstra merupakan salah satu varian bentuk algoritma popular dalam pemecahan persoalan terkait masalah optimasi pencarian  lintasan terpendek sebuah lintasan yang mempunyai panjang minimum dari verteks a ke z dalam graph berbobot, bobot tersebut adalah bilangan positif jadi tidak dapat dilalui oleh node negatif. Namun jika terjadi demikian, maka penyelesaian yang diberikan adalah infiniti (Tak Hingga). Pada algoritma Dijkstra, node digunakan karena algoritma Dijkstra menggunakan graph berarah untuk penentuan rute listasan terpendek. Berikut Pseudo Code dan Flowchart Algoritma Djikstra:

Djikstra Flowchart

Pseudo Code

	function Dijkstra(Graph, source):
	for each vertex v in Graph:                                // Initializations
	dist[v] := infinity ;                                  // Unknown distance function from
	// source to v
	previous[v] := undefined ;                             // Previous node in optimal path
	end for                                                    // from source
	dist[source] := 0 ;                                        // Distance from source to source
	Q := the set of all nodes in Graph ;                       // All nodes in the graph are
	// unoptimized - thus are in Q
	while Q is not empty:                                      // The main loop
	u := vertex in Q with smallest distance in dist[] ;    // Start node in first case
	remove u from Q ;
	if dist[u] = infinity:
	break ;                                            // all remaining vertices are
	end if                                                 // inaccessible from source
	for each neighbor v of u:                              // where v has not yet been
	// removed from Q.
	alt := dist[u] + dist_between(u, v) ;
	if alt < dist[v]:                                  // Relax (u,v,a)
	dist[v] := alt ;
	previous[v] := u ;
	decrease-key v in Q;                           // Reorder v in the Queue
	end if
	end for
	end while
	return dist;

view rawdjikstra.sh hosted with  by GitHub

Implementasi Djikstra

Algoritma ini bertujuan untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titk lainnya. Misalnya titik mengambarkan gedung dan garis menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik.

Pertama-tama tentukan titik mana yang akan menjadikan node awal, lalu beri bobot jarak pada node pertama ke node terdekat satu persatu, Dijkstra akan melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik selanjutnya tahap demi tahap inilah urutan logika dari algoritma Dijkstra :

1.      Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (belum terisi)

2.      Set semua node “Belum Terjamah” dan set node awal sebagai “Node keberangkatan”

3.      Dari no keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan. Sebagai contoh, jika titik keberangkatan A ke B memiliki bobot jarak 6 dan dari B ke node C berjarak 2, maka jarak ke C melewati B menjadi 6+2=8. Jika jarak ini lebih kecil dari jarak sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data jarak dengan jarak yang baru.

4.      Saat kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.

5.      Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selajutnya dan lanjutkan dengan kembali ke step 3

Note : Bahkan menurut Andrew Goldberg, peneliti utama di Microsoft Research Silicon Valley, mengatakan ada banyak alasan mengapa peneliti terus mempelajari masalah pencarian jalan terpendek.

“Jalan terpendek adalah masalah optimasi yang relevan untuk berbagai macam aplikasi, seperti jaringan routing, game, desain sirkuit, dan pemetaan,” – Goldberg. “Industri selalu datang dengan aplikasi baru sepanjang waktu, membuat parameter yang berbeda untuk tiap masalah.

Teknologi dengan lebih banyak kecepatan dan kapasitas memungkinkan kita untuk memecahkan masalah yang lebih besar, sehingga dalam lingkup masalah jalan terpendek maka akan selalu ada optimasi.

BAB III

KESIMPULAN

Berdasarkan latar belakang serta pembahasan-pembahasan pada bab sebelumnya, maka dapat disimpulkan bahwa :

a. Algoritma dijkstra dapat digunakan untuk mencari rute terpendek secara optimal.

b. Dengan menggunakan program ini dapat mempercepat dalam menentukan rute terpendek. c. Program ini menawarkan beberapa kemudahan dalam menyusun peta secara dinamik sehingga apabila terdapat perubahan kondisi pada peta, program dapat menyesuaikan dengan kondisi baru.

DAFTAR PUSTAKA

·         Anonim,2015 tentang Struktur data,

http://ndocfile.blogspot.co.id/2012/09/Struktur data diakses pada 25 Mei 2016 pada 02.31

·         Wisnu,2016 tentang Struktur data,

http://usniwisnu.blogspot.co.id/.html  diakses pada 25 Mei 2016 pada 02.40