Algoritma Dijkstra dalam Python & C++ (Contoh)

Apa yang dimaksud dengan Jalur Terpendek atau Jarak Terpendek?

Jalur dari simpul sumber ke simpul tujuan yang biayanya paling kecil disebut jalur terpendek atau jarak terpendek. Dalam teori graf, dimungkinkan untuk memiliki beberapa rute dari sumber ke tujuan. Di antara rute-rute ini, jika ada rute yang biayanya paling kecil, kita menyebutnya jalur terpendek.

Di sini, "biaya" berarti jumlah simpul dalam rute atau penjumlahan biaya pada setiap sisi. Suatu jalur dapat memiliki satu atau beberapa sisi. Koneksi antara dua simpul disebut "sisi". Terdapat berbagai jenis algoritma jalur terpendek, seperti Algoritma Dijkstra dan Algoritma Bellman-Ford.

Di sini, kita akan membahas Algoritma Dijkstra. Mari kita perhatikan grafik berbobot berikut:

Grafik Berbobot Tak Terarah

• Istilah “tertimbang” berarti biaya perpindahan dari satu node ke node lainnya. Misalnya, perpindahan dari node 1 ke node 2, biaya atau bobotnya adalah 1.
• Jalur antara node 1 dan node 2 disebut sisi (edge).
• “Tidak berarah” berarti Anda dapat berpindah dari satu node ke node lain dan kembali ke node sebelumnya. Jadi, jika kita mencoba menemukan semua rute dari node 1 ke node 7, rutenya akan menjadi:

Di antara keempat rute ini, kita dapat melihat bahwa rute pertama berbiaya 7. Jadi, ini adalah jalur terpendek dalam hal biaya.

Jalur Terpendek

Cara Kerja Algoritma Dijkstra

Algoritma Dijkstra dapat menemukan jarak terpendek pada graf berarah maupun tak berarah yang berbobot. Algoritma ini bersifat serakah karena selalu memilih simpul terpendek atau terdekat dari titik asal. Istilah "serakah" berarti bahwa di antara sekumpulan hasil, algoritma akan memilih yang terbaik.

Di sini, kita mencoba menemukan jalur terpendek di antara semua rute lainnya. Jadi, Algoritma Dijkstra menemukan semua jalur terpendek dari satu simpul sumber. Akibatnya, ia berperilaku seperti... algoritma serakah.

Pada bagian “contoh” di bawah ini, Anda akan melihat pendekatan langkah demi langkah. Cara kerjanya sebagai berikut:

Langkah 1) Inisialisasi node awal dengan biaya 0 dan node lainnya dengan biaya tak terhingga.
Langkah 2) Pertahankan array atau daftar untuk menyimpan track dari node yang dikunjungi.
Langkah 3) Perbarui biaya node dengan biaya minimum. Hal ini dapat dilakukan dengan membandingkan biaya saat ini dengan biaya jalur (seperti yang ditunjukkan pada 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 bahwa Dijkstra adalah algoritma pencarian jalur terpendek, sedangkan BFS dan DFS adalah algoritma pencarian jalur umum. Pada umumnya, BFS dan DFS tidak mempertimbangkan biaya tepi saat mencari jalur. Oleh karena itu, algoritma ini tidak dapat menjamin jalur terpendek.

Demonstrasi Grid 2D tentang Cara Kerja BFS

Sketsa Algo, menunjukkan demonstrasi 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.

Mari kita lihat contoh grafik:

Di sini, BFS menemukan jalur di level 2. BFS menelusuri grafik sesuai urutan level. Jadi, prosesnya seperti ini:

Langkah 1) Mulailah dari node “1” dan kunjungi semua node yang berdekatan yaitu 2, 3, 4.

Langkah 2) Tandai node 2, 3, 4 sebagai level 1 dan kunjungi node yang berdekatan. Program 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 kita lihat, DFS menghitung biaya jalurnya dengan jumlah sisi. 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, dalam hal Algoritma Dijkstra, algoritma ini memilih sisi berdasarkan biayanya. Sebagai algoritma greedy, ia akan memilih jalur dengan biaya 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.

Dalam Algoritma Dijkstra, algoritma ini akan menemukan jalur terpendek dengan menghitung bobot. Algoritma ini tidak akan mencari semua kemungkinan jalur. Mari kita demonstrasikan Algoritma Dijkstra dengan sebuah contoh. Misalnya, Anda diminta untuk menemukan jalur terpendek dari node 1 ke 7.

Untuk proses ini, langkah-langkahnya diberikan di bawah ini:

Langkah 1) Inisialisasi biaya node awal menjadi 0. Tetapkan “Inf” ke node lainnya. Artinya tidak ada jalur yang ada antara sumber dan node, atau jalur tersebut belum dikunjungi.

Langkah 2) Saat Anda memilih node 1, node tersebut akan ditandai sebagai sudah dikunjungi. Kemudian perbarui semua tetangga yang berdekatan dengan 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, kita berada di node 1, dan kita perlu memperbarui biaya node yang berdekatan, yaitu node 2, 3, dan 4. Setelah diperbarui, biaya akan terlihat seperti ini:

Langkah 3) Untuk node “2”, tetangganya adalah 6 dan 3. Kita memperbarui biaya di “6” dengan membandingkan tak terhingga (nilai saat ini) dengan biaya node 2 + biaya jalur dari 2 ke 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 node 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 menemukan jalur dari node 1 ke node 7, yaitu 1→3→7. Biayanya adalah 8.

Langkah 5) Untuk node 4, kita akan memperbarui biaya node yang berdekatan dengannya. Jadi, node “5” akan memiliki biaya yang diperbarui menjadi 8. Setelah langkah 4 dan 5, hasilnya akan terlihat seperti ini:

Sekarang, jalur 1-3-7 memiliki biaya 8 (sebelumnya). Node “7” tidak ditandai sebagai sudah 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, jalur terpendek dari simpul sumber “1” ke simpul tujuan “7” adalah 1-2-6-7, dan biayanya adalah 7. Sebelumnya jalurnya 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.

Pseudo Code Algoritma Dijkstra

Berikut adalah pseudokode untuk Algoritma Dijkstra:

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- U
  return distance, previous

C++ Implementasi Algoritma Dijkstra

Untuk mengimplementasikan algoritma Dijkstra menggunakan C++Berikut 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] && 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] && graph[U][j] &&
          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 PythonBerikut 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] <= _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 < 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 tersebut menghitung jarak terpendek dari node sumber.

Penerapan Algoritma Dijkstra

Algoritma Dijkstra memiliki banyak kegunaan. Di antaranya, algoritma ini banyak digunakan di bidang jaringan. Berikut beberapa contoh penggunaan Algoritma Dijkstra dalam kehidupan nyata:

Dijkstra di Google Peta: Algoritma ini adalah tulang punggung untuk menemukan jalur terpendek, seperti yang dapat kita lihat dari cuplikan kode di atas.

Google tidak menggunakan algoritma Dijkstra sederhana. Sebaliknya, ia menggunakan versi yang dimodifikasi. Saat Anda memilih tujuan, ia akan menampilkan beberapa jalur kepada Anda. Google Peta. Di antara jalur-jalur ini, beberapa diurutkan untuk pengguna. Jalur-jalur ini dipilih berdasarkan "waktu". Jadi, "waktu" adalah biaya tepi untuk jalur terpendek.

Dijkstra dalam Perutean IP: perutean IP IP routing adalah terminologi jaringan. Istilah ini menjelaskan bagaimana paket data Anda dikirim ke penerima melalui berbagai jalur. Jalur-jalur ini terdiri dari router, server, dan peralatan lainnya. Dalam IP routing, terdapat berbagai jenis protokol.

Protokol-protokol ini membantu router menemukan jalur terpendek untuk mengirim data. Salah satu nama protokol tersebut adalah “OSPF (Open Shortest Path First)”. OSPF menggunakan algoritma Dijkstra. Router memelihara tabel rute. Setiap router membagikan 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 jalur terpendek dalam graf dengan sisi negatif. Algoritma Dijkstra mengikuti prinsip-prinsip 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.

Pada grafik sebelah kiri, Terdapat tiga simpul. Algoritma Dijkstra akan berjalan pada graf seperti berikut:

Langkah 1) Titik awal “1” akan diinisialisasi ke nol. Node lainnya akan memiliki tak terhingga.

Langkah 2) Tandai node “1” sebagai node yang telah dikunjungi dan sertakan dalam jalur terpendek.

Langkah 3) Jarak dari node sumber 1 ke node “2” dan “3” ditetapkan sebagai tak terhingga, karena jalur terpendek belum dihitung. Jadi, jalur apa pun yang biayanya kurang dari tak terhingga akan ditambahkan ke jalur terpendek (pendekatan serakah).

Langkah 4) Memperbarui jarak dari simpul sumber “1” ke “2”. Bobot saat ini adalah 5 (5 < tak terhingga). Demikian pula, perbarui jarak dari simpul “1” ke “3” dengan bobot 3.

Langkah 5) Sekarang, jika kita memeriksa jarak terpendek dari node “1”, kita menemukan bahwa 5 adalah jarak terpendek untuk sisi 1→2. Jadi, node “2” akan ditandai sebagai telah dikunjungi. Demikian pula, node “3” juga akan ditandai sebagai telah dikunjungi karena jarak terpendeknya adalah 3.

Namun, jika kita amati, ada jalur 1-3-2 yang hanya membutuhkan biaya 2. Tetapi Dijkstra menunjukkan bahwa dari simpul "1" ke simpul "2", jarak terpendek adalah 5. Jadi, Dijkstra gagal menghitung jarak terpendek dengan benar. Alasannya adalah Dijkstra merupakan algoritma greedy. Jadi, begitu sebuah simpul ditandai sebagai telah dikunjungi, simpul tersebut tidak akan dipertimbangkan lagi, meskipun mungkin ada jalur yang lebih pendek. Masalah ini hanya terjadi ketika sisi-sisi memiliki biaya negatif atau bobot negatif.

Algoritma Dijkstra gagal menghitung jalur terpendek antara dua node dalam skenario ini. Akibatnya, algoritma ini memiliki beberapa kekurangan. Untuk mengatasi masalah sisi negatif ini, digunakan algoritma lain yang disebut "Algoritma Bellman-Ford". 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 O(V²)Di sini, istilah “O” adalah notasi yang memberikan asumsi untuk algoritma Dijkstra.

Kita dapat menyimpan graf menggunakan "antrian prioritas". Antrian prioritas adalah struktur data heap biner. Ini akan lebih efisien daripada matriks 2D. Sebuah sisi dengan biaya minimum akan memiliki prioritas tinggi. Maka kompleksitas waktunya akan menjadi... O(log E). Di sini, E adalah jumlah sisi, dan V adalah jumlah simpul.

Kompleksitas ruang adalah O(V²), karena kita menggunakan matriks ketetanggaan (Array 2DKompleksitas ruang dapat dioptimalkan menggunakan daftar kedekatan atau struktur data antrean.

Pertanyaan Umum Demo Slot