Algoritma Dijkstra

November 12, 2019

Algoritma Dijkstra

Sebelumnya mungkin masih banyak yang belum tau apa itu algoritma dijkstra, algoritma dijkstra di gunakan untuk mencari sebuah jalan atau rute terdekat (terpendek) yang lebih mudah dan lebih cepat mencapai sebuah tujuan . di sini saya sedikit akan membahas tentang pengertian apa itu algoritma dijkstra dan cara kerja-nya.

Edsger W. Dikstra adalah orang pertama yang menemukan teori Algoritma Dijkstra,Algortitma Dijkstra adalah sebuah algoritme rakus (greedy algorithm) yang dimana digunakan untuk memecahkan sebuah permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot garis (edge weights) yang bernilai nonnegatif{\displaystyle [0,\infty )}. Input algoritme ini adalah sebuah graf berarah yang berbobot dan sebuah titik asal

s

dalam himpunan garis $V$ .

Misalnya, bila titik dari sebuah graf melambangkan kota-kota dan bobot garis melambangkan jarak antara kota-kota tersebut, algoritme Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota. bobot tersebut adalah bilangan positif jadi tidak dapat dilalui oleh node negatif. Namun jika terjadi demikian, maka penyelesaian yang diberikan adalah infiniti (Tak Hingga).

Algoritma Dijkstra mulai di perkenalkan kepada masyarakat pada tahun 1959. Edsger memperkenalkan algoritma melalui sebuah media jurnal Numerische Mathematik yang berjudul “A Note on Two Problems in Connexion with Graphs“. Algoritma ini sering digambarkan sebagai algoritma greedy (tamak). Sebagai contoh, ada pada buku Algorithmics (Brassard and Bratley [1988, pp. 87-92])

Pada algoritma Dijkstra, node digunakan karena algoritma Dijkstra menggunakan graph berarah untuk penentuan rute listasan terpendek. Berikut Pseudo Code dan Flowchart Algoritma Djikstra:

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

Diskripsi matematis untuk grafik dapat diwakili G = {V. E}, yang berarti sebuah grafik (G) didefenisikan oleh satu set simpul (Vertex = V) dan koleksi Edge (E).

Algoritma Dijkstra bekerja dengan membuat jalur ke satu simpul optimal pada setiap langkah. Jadi pada langkah ke n, setidaknya ada n node yang sudah kita tahu jalur terpendek. Langkah-langkah algoritma Dijkstra dapat dilakukan dengan langkah-langkah berikut:

1. Tentukan titik mana yang akan menjadi node awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, Dijkstra akan melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik selanjutnya tahap demi tahap.

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

3. Set semua node yang belum dilalui dan set node awal sebagai “Node keberangkatan”

4. Dari node keberangkatan, pertimbangkan node tetangga yang belum dilalui dan hitung jaraknya dari titik keberangkatan. Jika jarak ini lebih kecil dari jarak sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data jarak dengan jarak yang baru

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

6. Set “Node belum dilewati” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan ulangi langkah e.

Sebagai contoh hitunglah Jarak terdekat dari V1 ke V7 pada gambar berikut ini.