Algoritma Dijkstra
Terakhir diperbarui
Algoritma Dijkstra adalah algoritma untuk mencari jalur terpendek dari sebuah node sumber ke setiap node lain pada graf dengan bobot edge yang tidak negatif. Algoritma ini menyimpan jarak sementara untuk setiap node, berulang kali menetapkan (settle) node belum tetap yang jarak sementaranya paling kecil, lalu merelaksasi edge-nya, yaitu memperbarui jarak sebuah tetangga setiap kali ditemukan rute yang lebih pendek lewat node saat ini. Tekan Putar di atas untuk melihat jarak turun saat setiap node ditetapkan.
Inti idenya bersifat greedy: begitu node belum tetap yang terdekat dipilih, jaraknya sudah final, karena semua rute lain menuju node itu harus melewati node yang sudah lebih jauh. Dengan priority queue berbasis binary heap, Dijkstra berjalan dalam waktu O((V + E) log V). Algoritma ini membutuhkan bobot yang tidak negatif; pakai Bellman-Ford jika edge bisa bernilai negatif.
Kompleksitas waktu dan ruang
| Implementasi | Kompleksitas | Catatan |
|---|---|---|
| Binary heap | O((V + E) log V) | Pilihan umum yang praktis |
| Pemindaian array | O(V²) | Lebih sederhana; cocok untuk graf padat |
| Ruang | O(V) | Jarak + priority queue |
| Membutuhkan | Bobot tidak negatif | Edge negatif merusak pilihan greedy |
Langkah demi langkah
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Atur jarak sumber ke 0 dan semua jarak lainnya ke tak hingga. |
| 2 | Pilih node belum tetap dengan jarak sementara paling kecil. |
| 3 | Tandai sudah tetap: jarak terpendeknya kini final. |
| 4 | Untuk setiap tetangga, hitung jarak lewat node saat ini + bobot edge. |
| 5 | Jika hasilnya lebih kecil daripada jarak tetangga saat ini, relaksasi. |
| 6 | Ulangi sampai semua node yang bisa dicapai sudah tetap. |
Contoh penerapan
Jalur terpendek dari sumber A pada graf dengan edge A-B=4, A-C=1, C-B=2, C-D=5, B-D=1:
| Langkah | Ditetapkan | Jarak | Aksi |
|---|---|---|---|
| 0 | - | A=0, B=∞, C=∞, D=∞ | Inisialisasi: sumber A=0, semua lainnya tak hingga. |
| 1 | A (0) | B=4, C=1, D=∞ | Relaksasi edge dari A: atur B=4, C=1. |
| 2 | C (1) | B=3, D=6 | Lewat C: B=1+2=3 mengalahkan 4; D=1+5=6. |
| 3 | B (3) | D=4 | Lewat B: D=3+1=4 mengalahkan 6. |
| 4 | D (4) | A=0, C=1, B=3, D=4 | Tetapkan D; tidak ada lagi yang perlu direlaksasi. Selesai. |
Kapan memakai algoritma Dijkstra
| Pakai saat | Hindari saat |
|---|---|
| Semua bobot edge tidak negatif | Ada edge yang bisa negatif: pakai Bellman-Ford |
| Kamu butuh jalur terpendek dari satu sumber ke semua node | Kamu butuh jalur terpendek untuk semua pasangan: Floyd-Warshall lebih sederhana |
| Grafnya berbobot dan kamu ingin jarak yang tepat | Grafnya tak berbobot: BFS biasa lebih cepat dan lebih sederhana |
| Kamu punya heap/priority queue yang bagus | Kamu ingin mencapai satu target dengan cepat memakai heuristik: pakai A* |
Kode Dijkstra's Algorithm
Implementasi Dijkstra's Algorithm yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Dijkstra's Algorithm dalam Python
1import heapq2
3
4def dijkstra(graph, start):5 dist = {node: float("inf") for node in graph}6 dist[start] = 07 pq = [(0, start)]8 while pq:9 d, node = heapq.heappop(pq)10 if d > dist[node]:11 continue # stale entry, a shorter path was already found12 for neighbor, weight in graph[node]:13 new_dist = d + weight14 if new_dist < dist[neighbor]:15 dist[neighbor] = new_dist16 heapq.heappush(pq, (new_dist, neighbor))17 return dist18
19
20graph = {21 "A": [("B", 4), ("C", 1)],22 "B": [("D", 1)],23 "C": [("B", 2), ("D", 5)],24 "D": [("E", 3)],25 "E": [],26}27
28for node, d in dijkstra(graph, "A").items():29 print(f"A -> {node}: {d}")Kode Dijkstra's Algorithm dalam JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { C: 5, D: 10 },4 C: { E: 3 },5 D: { F: 11 },6 E: { D: 4 },7 F: {},8};9
10function dijkstra(source) {11 const dist = {};12 const visited = new Set();13 for (const node in graph) dist[node] = Infinity;14 dist[source] = 0;15 while (visited.size < Object.keys(graph).length) {16 // JS has no built-in heap: linear scan for the closest node (O(V^2))17 let u = null;18 for (const node in dist) {19 if (!visited.has(node) && (u === null || dist[node] < dist[u])) {20 u = node;21 }22 }23 if (dist[u] === Infinity) break;24 visited.add(u);25 for (const [v, w] of Object.entries(graph[u])) {26 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;27 }28 }29 return dist;30}31
32console.log("Shortest distances from A:", dijkstra("A"));Kode Dijkstra's Algorithm dalam Java
1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4import java.util.PriorityQueue;5
6public class Main {7 public static void main(String[] args) {8 int n = 6;9 List<List<int[]>> adj = new ArrayList<>();10 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());11 int[][] edges = {12 {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5},13 {2, 3, 8}, {3, 4, 3}, {2, 5, 10}, {4, 5, 2}14 };15 for (int[] e : edges) {16 adj.get(e[0]).add(new int[]{e[1], e[2]});17 adj.get(e[1]).add(new int[]{e[0], e[2]});18 }19
20 int[] dist = new int[n];21 Arrays.fill(dist, Integer.MAX_VALUE);22 dist[0] = 0;23 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);24 pq.add(new int[]{0, 0}); // {node, distance}25 while (!pq.isEmpty()) {26 int[] cur = pq.poll();27 int node = cur[0], d = cur[1];28 if (d > dist[node]) continue; // stale queue entry29 for (int[] edge : adj.get(node)) {30 int next = edge[0], nd = d + edge[1];31 if (nd < dist[next]) {32 dist[next] = nd;33 pq.add(new int[]{next, nd});34 }35 }36 }37 System.out.println("Shortest distances from 0: " + Arrays.toString(dist));38 }39}Kode Dijkstra's Algorithm dalam C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 const int INF = 1000000000;7 // Weighted directed graph: adj[u] = {(neighbor, weight), ...}8 std::vector<std::vector<std::pair<int, int>>> adj = {9 {{1, 4}, {2, 1}}, // 010 {{3, 1}}, // 111 {{1, 2}, {3, 5}}, // 212 {{4, 3}}, // 313 {}, // 414 };15 int n = static_cast<int>(adj.size());16 std::vector<int> dist(n, INF);17 dist[0] = 0;18 using State = std::pair<int, int>; // (distance, node)19 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;20 pq.push({0, 0});21 while (!pq.empty()) {22 auto [d, u] = pq.top();23 pq.pop();24 if (d > dist[u]) continue; // stale queue entry25 for (auto [v, w] : adj[u]) {26 if (d + w < dist[v]) {27 dist[v] = d + w;28 pq.push({dist[v], v});29 }30 }31 }32 for (int v = 0; v < n; ++v) {33 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";34 }35 return 0;36}Kode Dijkstra's Algorithm dalam C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Weighted directed graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 4, 1, 0, 0},11 {0, 0, 0, 1, 0},12 {0, 2, 0, 5, 0},13 {0, 0, 0, 0, 3},14 {0, 0, 0, 0, 0},15 };16 int dist[N];17 bool done[N] = {false};18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // O(V^2) scan for the closest unfinished node (no heap needed here)21 for (int iter = 0; iter < N; iter++) {22 int u = -1;23 for (int v = 0; v < N; v++) {24 if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;25 }26 if (dist[u] == INF) break; // remaining nodes are unreachable27 done[u] = true;28 for (int v = 0; v < N; v++) {29 if (w[u][v] > 0 && dist[u] + w[u][v] < dist[v]) {30 dist[v] = dist[u] + w[u][v];31 }32 }33 }34 for (int v = 0; v < N; v++) {35 printf("Distance 0 -> %d: %d\n", v, dist[v]);36 }37 return 0;38}FAQ Algoritma Dijkstra
Berapa kompleksitas waktu algoritma Dijkstra?
O((V + E) log V). Versi sederhana yang memindai array untuk mencari nilai minimum di setiap langkah bernilai O(V²), dan versi ini justru bisa lebih cepat pada graf yang padat. Keduanya memakai ruang O(V).Mengapa Dijkstra tidak bekerja dengan bobot edge negatif?
Dijkstra berasumsi bahwa begitu node belum tetap yang terdekat ditetapkan, jaraknya sudah final. Edge negatif bisa kemudian menciptakan jalur yang lebih pendek ke node yang sudah ditetapkan, sehingga asumsi itu runtuh. Untuk graf dengan bobot negatif, pakai algoritma Bellman-Ford.
Apa perbedaan Dijkstra dan BFS?
BFS mencari jalur terpendek dengan menghitung jumlah edge (setiap bobot edge pada dasarnya bernilai 1), memakai queue biasa. Dijkstra memperluas ide ini ke graf berbobot dengan selalu memperluas node yang total jaraknya paling kecil, memakai priority queue. Pada graf tak berbobot, keduanya menghasilkan jalur yang sama.
Apa perbedaan Dijkstra dan pencarian A*?
A* adalah Dijkstra ditambah heuristik yang memperkirakan sisa jarak ke target, sehingga pencarian diarahkan ke tujuan itu alih-alih meluas secara merata ke segala arah. Jika heuristiknya nol, A* menjadi persis sama dengan Dijkstra. Pakai A* saat kamu punya satu tujuan dan heuristik admissible yang bagus; pakai Dijkstra saat kamu butuh jarak ke setiap node.
Kapan sebaiknya memakai Dijkstra, bukan Bellman-Ford?
O((V + E) log V) dibandingkan O(V·E) milik Bellman-Ford. Pilih Bellman-Ford hanya saat edge bisa negatif atau kamu perlu mendeteksi siklus negatif. Pada graf dengan bobot tidak negatif, Dijkstra hampir selalu pilihan yang lebih baik.Bisakah Dijkstra mengunjungi ulang node yang sudah ditetapkan?
Tidak. Begitu sebuah node ditetapkan, jaraknya sudah final dan tidak pernah direlaksasi lagi. Jebakan yang umum pada implementasi heap adalah membiarkan entri usang di priority queue setelah jarak sebuah node membaik; kamu harus melewati node hasil pop jika node itu sudah ditetapkan (jarak hasil pop-nya melebihi jarak yang tercatat). Lupa melakukan pengecekan ini tetap menghasilkan jawaban yang benar, tetapi membuang kerja.
Sumber terkait
Visualisasi lainnya
