Algoritma Dijsktra : C++, Python Contoh Kode
Sarah Chen
Apa jalur terpendek atau jarak terpendek?
Jalur dari simpul sumber ke simpul tujuan yang biayanya minimum adalah jalur terpendek atau jarak terpendek. Dalam teori graf, dimungkinkan untuk memiliki banyak rute dari sumber ke tujuan. Di antara rute-rute tersebut, jika ada rute yang biayanya minimal, kita dapat menyebutnya sebagai algoritma jalur terpendek.
Di sini “Biaya” berarti jumlah node dalam rute atau penjumlahan biaya pada setiap jalur. Sebuah jalur dapat memiliki satu atau beberapa sisi. Hubungan antara dua simpul disebut “tepi”. Ada berbagai jenis algoritma jalur terpendek, seperti Algoritma Dijkstra, algoritma Bellman-Ford, dll.
Disini kita akan membahas tentang Algoritma Dijkstra
Mari kita lihat Grafik tertimbang berikut:
- Istilah “Tertimbang” berarti memindahkan biaya dari satu node ke node lainnya. Misalnya berpindah dari node 1 ke node 2 maka biaya atau bobotnya adalah 1.
- Jalur antara node 1 ke node 2 disebut edge.
- “Tidak terarah” berarti Anda dapat memindahkan satu node ke node lainnya dan kembali ke node sebelumnya. Jadi, jika kita mencoba mencari semua rute dari node 1 hingga node 7, maka hasilnya akan menjadi:
| Rute atau Jalur | Biaya |
|---|---|
| +1 2 6 | (1+3+3) = 7 |
| +1 2 3 | (1+9+1) = 11 |
| 1-3-7 | (7+1) = 8 |
| +1 4 5 | (6+2+5) = 13 |
Di antara keempat rute tersebut, kita dapat melihat bahwa rute pertama akan memakan biaya 7. Jadi, ini adalah jalur terpendek dari segi biaya.
Cara Kerja Algoritma Dijkstra
Algoritma Dijkstra dapat mencari jarak terpendek pada graf berbobot berarah dan tidak berarah. Algoritma ini bersifat serakah karena selalu memilih node terpendek atau terdekat dari titik asal. Istilah “serakah” berarti bahwa di antara serangkaian hasil atau hasil, Algoritma akan memilih yang terbaik di antara hasil tersebut.
Di sini, kami mencoba mencari jalur terpendek di antara semua rute lainnya. Jadi, Algoritma Dijkstra menemukan semua jalur terpendek dari satu node tujuan. Akibatnya, ia berperilaku seperti a algoritma serakah.
Di bagian “contoh” di bawah, Anda akan melihat pendekatan langkah demi langkah. Ini berfungsi sebagai berikut:
Langkah 1) Inisialisasi node awal dengan biaya 0 dan node lainnya sebagai Biaya Tak Terhingga.
Langkah 2) Pertahankan array atau daftar untuk melacak node yang dikunjungi
Langkah 3) Perbarui biaya node dengan biaya minimum. Hal ini dapat dilakukan dengan membandingkan biaya saat ini dengan biaya jalur. (Demonstrasi ditunjukkan di bagian contoh)
Langkah 4) Lanjutkan langkah 3 hingga semua node dikunjungi.
Setelah menyelesaikan semua langkah ini, kita akan menemukan jalur dengan biaya minimum dari sumber ke tujuan.
Perbedaan Antara Dijkstra dan BFS, DFS
Perbedaan utama antara Dijkstra dan BFS-DFS adalah Dijkstra adalah algoritma pencarian jalan terpendek, dan BFS, DFS adalah algoritma pencarian jalan. Dalam kasus umum, BFS dan DFS tidak mempertimbangkan biaya saat mencari jalur. Jadi, algoritma ini tidak dapat menjamin jalur terpendek.
Demonstrasi grid 2D tentang cara kerja BFS
Demonstrasi ini menunjukkan bahwa BFS hanya menemukan jalannya. Namun, ia tidak peduli dengan bobot jalurnya. BFS (Pencarian Luas-Pertama) mengasumsikan bahwa perjalanan dari satu node ke node lain hanya akan memakan biaya 1.
Tapi mari kita lihat contoh grafiknya:
Di sini, ia menemukan jalur di level 2. BFS melintasi Grafik dalam urutan level. Jadi, perjalanannya seperti:
Langkah 1) Mulai dari node “1” dan kunjungi semua node 2,3,4 yang berdekatan
Langkah 2) Tandai node 2,3,4 sebagai level 1 dan kunjungi node yang berdekatan. Ia akan terus menjelajahi semua node yang berdekatan hingga mencapai node tujuan.
Dalam istilah DFS, ia akan melintasi jalur dari 1 hingga 7 seperti berikut:
- 1→2→3→7 (Biaya Asli 10, biaya DFS 3)
- 1→2→6→7 (Biaya Asli 7, biaya DFS 3)
- 1→3→7 (Biaya Asli 8, biaya DFS 2)
- 1→4→5→7 (Biaya Asli 13, biaya DFS 3)
Seperti yang bisa kita lihat, DFS menghitung biaya jalurnya dengan jumlah kedalaman atau jumlah tepi.
DFS melakukan hal berikut:
- DFS dapat menemukan jalur dari sumber (simpul awal) ke tujuan.
- Ia tidak dapat menjamin apakah jalur yang ditemukan dari node sumber ke node tujuan merupakan jalur terpendek atau bukan.
Namun pada Algoritma Dijkstra akan memilih edge berdasarkan biayanya. Sebagai algoritma serakah, ia akan memilih jalur biaya terbaik atau minimum.
Contoh Algoritma Dijkstra
Algoritma Dijkstra menggunakan biaya atau bobot untuk menghitung total biaya jalur.
Target dari Algoritma Dijkstra adalah meminimalkan total biaya atau bobot tersebut. Pada contoh di atas, kita mencari jalur terbaik dari node 1 ke node 7, lalu menghitung semua biayanya.
Pada Algoritma Dijkstra akan dicari jalur terpendek dengan menghitung bobot. Itu tidak akan mencari semua jalur yang mungkin. Mari kita tunjukkan Algoritma Dijkstra dengan sebuah contoh. Misalnya, Anda diminta mencari jalur terpendek dari node 1 hingga 7.
Untuk proses ini, langkah-langkahnya diberikan di bawah ini:
Langkah 1) Inisialisasi biaya node awal ke 0.
Node lainnya, tetapkan “Informasi”. Artinya tidak ada jalur yang ada antara titik awal (sumber) dan node, atau jalur tersebut belum dikunjungi.
Langkah 2) Saat Anda memilih node 1, node tersebut akan ditandai sebagai telah dikunjungi. Kemudian perbarui semua tetangga yang berdekatan dari node 1. 2,3,4 adalah node tetangga dari node 1.
Saat memperbarui biaya, kita perlu mengikuti prosedur di bawah ini:
Kita dapat memperbarui biaya setiap node menggunakan rumus di atas. Misalnya, kami berada di node 1, dan kami perlu memperbarui biaya node 2,3,4 yang berdekatan.
Setelah diperbarui, biaya atau beratnya akan terlihat seperti ini:
Langkah 3) Untuk simpul “2”, tetangganya adalah 6 dan 3. Kami memperbarui biaya pada “6” dengan membandingkan tak terhingga (nilai saat ini). Biaya node 2 + biaya jalur dari 2 hingga 6. Sederhananya, node “6” akan memiliki biaya 1+3 atau 4.
Node 3 adalah tetangga dari node 2. Namun, kita menghitung biayanya pada langkah sebelumnya, yaitu 7. Sekarang, jika jalur kita adalah 1-2-3, maka node 3 akan memiliki biaya 10. Jalur 1-2- 3 berharga 10, sedangkan 1 hingga 3 berharga 7.
Langkah 4) Untuk simpul 3, node tetangganya adalah 7. Jadi, dengan membandingkan nilai node 7 saat ini dengan biaya jalur (7+1) atau 8, kita akan memperbarui biaya node 7. Yaitu 8.
Jadi, kita cari jalur dari node 1 ke node 7, dan jalurnya adalah 1→ 3→ 7. Biayanya 8.
Langkah 5) Untuk simpul 4, kami akan memperbarui biaya node yang berdekatan. Jadi, node “5” akan memiliki biaya yang diperbarui sebesar 8. Setelah langkah 4,5, akan terlihat seperti ini:
Sekarang jalur 1-3-7 memiliki biaya 8 (sebelumnya). Node “7” tidak ditandai sebagai dikunjungi karena kita dapat mencapai node “7” dari node “6”. Jalur “1-2-6” memiliki biaya 4. Jadi jalur 1-2-6-7 akan memiliki biaya 7.
Karena 7 < 8, maka jalur terpendek dari simpul sumber “1” ke simpul tujuan “7” adalah 1-2-6-7, dan biayanya adalah 7. Sebelumnya adalah 1-3-7, dan biayanya adalah 8.
Jadi, Grafik akhirnya akan terlihat seperti ini:
Tepi yang ditandai dengan garis hitam adalah jalur terpendek kita dari 1 sampai 7, dan biayanya 7.
Algoritma Pseudo Code Dijkstra
Berikut pseudo-code Algoritma Dijkstra
Dijkstra(G, S):
for each vertex V in G
distance[V] & lt; - Infinity
previous[V] & lt; - NULL
if V does not equal S, then,
(priority queue) Q.push(V)
distance[S] = 0
While Q is not empty
U & lt; - Extract the MIN from Q
For each unvisited adjacent V of U
TotalDistance & lt; - distance[U] + edge_cost(U, V)
if TotalDistance is less than distance[V], then
distance[V] & lt; - TotalDistance
previous[V] & lt; - u
return distance, previous
C++ implementasi Algoritma Dijkstra
Untuk mengimplementasikan algoritma Dijkstra menggunakan C++, ini kodenya:
#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
int min = INT_MAX;
int min_index = INT_MAX;
for (int i = 0; i < size; i++) {
if (!visited[i] & amp; & distance[i] <= min) {
min = distance[i];
min_index = i;
}
}
return min_index;
}
void printParentPath(int parent[], int i) {
if (parent[i] == -1) {
return;
}
printParentPath(parent, parent[i]);
cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
int distance[size];
bool visited[size];
int parent[size];
for (int i = 0; i < size; i++) {
parent[0] = -1;
distance[i] = INT_MAX;
visited[i] = false;
}
distance[source] = 0;
for (int i = 0; i < size - 1; i++) {
int U = minimumDistance(distance, visited);
visited[U] = true;
for (int j = 0; j < size; j++) {
int curr_distance = distance[U] + graph[U][j];
if (!visited[j] & amp; & graph[U][j] & amp; &
curr_distance < distance[j]) {
parent[j] = U;
distance[j] = curr_distance;
}
}
}
cout << "Vertex\t\tDistance\tPath" << endl;
for (int i = 1; i < size; i++) {
cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
<< source + 1 << " ";
printParentPath(parent, i);
cout << endl;
}
}
int main() {
int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
{7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
{0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
{0, 0, 0, 0, 5, 3, 0}};
dijkstra(graph, 0);
}
Keluaran:
Vertex Distance Path 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Python implementasi Algoritma Dijkstra
Untuk mengimplementasikan algoritma Dijkstra menggunakan ular sanca, ini kodenya:
num_of_vertex = 7
def minimumDistance(distance, visited):
_min = 1e11
min_index = 1e11
for i in range(num_of_vertex):
if not visited[i] and distance[i] & lt; = _min:
_min = distance[i]
min_index = i
return min_index
def printParentNode(parent, i):
if parent[i] == -1:
return
printParentNode(parent, parent[i])
print("{} ".format(i + 1), end = "")
def dijkstra(graph, src):
distance = list()
visited = list()
parent = list()
for i in range(num_of_vertex):
parent.append(-1)
distance.append(1e11)
visited.append(False)
distance[src] = 0
for i in range(num_of_vertex - 1):
U = minimumDistance(distance, visited)
visited[U] = True
for j in range(num_of_vertex):
curr_distance = distance[U] + graph[U][j]
if not visited[j] and graph[U][j] and curr_distance & lt;
distance[j]: parent[j] = U
distance[j] = curr_distance
print("Vertex\t\tDistance\tPath")
for i in range(num_of_vertex):
print("{}->{}\t\t{}\t\t{}
".format(src + 1, i + 1, distance[i], src + 1), end = "")
printParentNode(parent, i)
print("")
graph = [
[0, 1, 7, 6, 0, 0, 0],
[1, 0, 9, 0, 0, 3, 0],
[7, 9, 0, 0, 0, 0, 1],
[6, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 2, 0, 0, 0],
[0, 3, 0, 0, 0, 0, 3],
[0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)
Keluaran:
Vertex Distance Path 1->1 0 1 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Kita dapat melihat bahwa Algoritma menghitung jarak terpendek dari node sumber.
Penerapan Algoritma Dijkstra
Dijkstra Algo memiliki banyak kegunaan. Diantaranya banyak digunakan di bidang jaringan. Berikut beberapa penggunaan Algoritma Dijkstra dalam kehidupan nyata:
Dijkstra di peta Google: Pada dasarnya Algoritma ini merupakan tulang punggung dalam mencari jalur terpendek. Seperti yang bisa kita lihat dari keluaran cuplikan kode di atas.
Google tidak menggunakan algoritma Dijkstra yang sederhana. Sebaliknya, ia menggunakan versi yang dimodifikasi. Saat Anda memilih tujuan, ini menunjukkan beberapa jalur di Google Map. Di antara jalur-jalur ini, beberapa jalur diurutkan untuk pengguna. Jalur yang dipilih ini didasarkan pada “waktu”. Jadi, “waktu” adalah biaya tambahan untuk jalur terpendek.
Dijkstra dalam perutean IP: perutean IP adalah terminologi jaringan. Artinya bagaimana paket data Anda dikirim ke penerima melalui jalur yang berbeda. Jalur ini terdiri dari router, server, dll. Dalam perutean IP, terdapat berbagai jenis protokol.
Protokol ini membantu router menemukan jalur terpendek untuk mengirim data. Salah satu nama protokolnya adalah “OSPF (Open Shortest Path First)”. OSPF menggunakan algoritma dijkstra. Router menyimpan tabel rute. Setiap router berbagi tabelnya dengan router tetangga. Setelah menerima tabel yang diperbarui, mereka harus menghitung semua jalur lagi. Pada saat itu, router menggunakan Algoritma Dijkstra.
Batasan Algoritma Dijkstra
Algoritma Dijkstra tidak dapat menjamin adanya jalur terpendek pada graf tepi negatif. Algoritma Dijkstra mengikuti metodologi berikut:
- Satu jalur terpendek akan ditempuh dari satu node ke node lainnya.
- Setelah jalur terpendek antara dua node dipilih, jalur tersebut tidak akan dihitung lagi.
Di sini, perhatikan dua contoh dengan sisi negatif.
Di Grafik kiri, ada tiga titik sudut. Dijkstra akan menjalankan Graph seperti berikut:
Langkah 1) Titik awal “1” akan diinisialisasi ke nol. Node lainnya akan memiliki tak terhingga.
Langkah 2) Tandai Node “1” sebagai telah dikunjungi dan sertakan dalam jalur terpendek.
Langkah 3) Jarak dari node sumber 1 ke node “2” dan “3” diatur ke tak terhingga, karena jalur terpendeknya belum dihitung. Jadi, jalur mana pun yang biayanya kurang dari tak terhingga akan ditambahkan ke jalur terpendek (pendekatan serakah).
Langkah 4) Memperbarui jarak dari simpul sumber atau simpul sumber “1” ke “2”. Berat saat ini akan menjadi 5 (5
Langkah 5) Sekarang jika kita memeriksa jarak terpendek dari node “1”, kita menemukan bahwa 5 adalah jarak terpendek untuk tepi 1–> 2. Jadi, node “2” akan ditandai sebagai telah dikunjungi.
Demikian pula, node “3” juga akan ditandai sebagai dikunjungi karena jarak terpendeknya adalah 3.
Namun jika kita amati, ada jalur 1-3-2 yang biayanya hanya 2. Namun Dijkstra menunjukkan bahwa dari node “1” ke node “2”, jarak terpendeknya adalah 5. Jadi, Dijkstra gagal menghitung jarak terpendek. jarak dengan benar. Alasan terjadinya hal ini adalah karena Dijkstra adalah algoritma yang serakah. Jadi, setelah sebuah node ditandai telah dikunjungi, node tersebut tidak akan dipertimbangkan kembali, meskipun mungkin tersedia jalur yang lebih pendek. Masalah ini hanya terjadi jika edge memiliki biaya negatif atau edge berbobot negatif
Dijkstra gagal menghitung jalur terpendek antara dua node dalam skenario ini. Oleh karena itu, Algoritma ini mempunyai beberapa kelemahan. Untuk mengatasi masalah tepi negatif ini, algoritma lain yang disebut “Algoritma Bellman-Ford” digunakan. Algoritma tersebut dapat bekerja dengan sisi negatif.
Kompleksitas Algoritma Dijkstra
Implementasi di atas menggunakan dua loop “for”. Loop ini berjalan untuk jumlah verteks. Jadi, kompleksitas waktunya adalah HAI(V2). Di sini yang dimaksud dengan “0” adalah notasi yang memberikan asumsi terhadap algoritma Dijkstra.
Kita dapat menyimpan Grafik menggunakan “Antrian Prioritas”. Antrian prioritas adalah struktur data tumpukan biner. Ini akan lebih efisien daripada matriks 2D. Keunggulan yang memiliki biaya minimum akan memiliki prioritas tinggi.
Maka kompleksitas waktunya akan menjadi O (E log (V)). Di sini, E adalah jumlah sisi, dan V adalah jumlah simpul.
Kompleksitas ruang adalah HAI(V2), karena kita menggunakan matriks ketetanggaan (Array 2DKompleksitas ruang dapat dioptimalkan menggunakan daftar kedekatan atau struktur data antrean.
