Rangkuman: Dijkstra's Algorithm

Shortest Path Algorithm

1. Pengertian

Dijkstra's Algorithm adalah algoritma yang digunakan untuk menemukan **jalur terpendek dari satu simpul sumber (source vertex) ke semua simpul lainnya** dalam graf berbobot (weighted graph). Algoritma ini bekerja dengan mencari jalur dengan bobot total terkecil.

Penting: Dijkstra's Algorithm hanya bekerja dengan sisi yang memiliki **bobot positif**. Jika ada bobot negatif, algoritma seperti Bellman-Ford atau Floyd-Warshall harus digunakan.

2. Konsep Dasar & Mekanisme

Dijkstra's Algorithm menggunakan pendekatan greedy. Algoritma ini menjaga sekumpulan simpul yang jarak terpendeknya dari sumber sudah diketahui dan memperbarui jarak ke simpul-simpul yang belum dikunjungi. Ia menggunakan sebuah Priority Queue (min-heap) untuk secara efisien mengambil simpul dengan jarak terpendek yang diketahui berikutnya.

Langkah-langkah Algoritma:

Inisialisasi jarak ke simpul sumber menjadi 0, dan jarak ke semua simpul lainnya menjadi tak terbatas (infinity).
Buat set (atau array boolean) `visited` untuk melacak simpul yang sudah dikunjungi, diinisialisasi kosong.
Buat Priority Queue (min-heap) dan masukkan simpul sumber dengan jarak 0.
Selama Priority Queue tidak kosong:
- Keluarkan simpul $U$ dari Priority Queue yang memiliki jarak terpendek saat ini.
- Jika $U$ sudah ada di `visited`, lewati (sudah diproses).
- Tambahkan $U$ ke `visited`.
- Untuk setiap tetangga $V$ dari $U$:
  - Hitung jarak baru ke $V$ melalui $U$: `jarak[U] + bobot_sisi(U, V)`.
  - Jika jarak baru ini lebih kecil dari `jarak[V]` yang sudah ada:
    - Perbarui `jarak[V]` dengan jarak baru.
    - Masukkan $V$ ke Priority Queue dengan jarak baru tersebut.
Setelah Priority Queue kosong, array `jarak` akan berisi jarak terpendek dari simpul sumber ke semua simpul lainnya.

3. Contoh Ilustrasi

Graf berikut (Simpul A-E, dengan bobot sisi):


    (0) --> (A) --5--> (C) --1--> (D)
     |       |          ^          ^
     10      3          |          |
     |       |          2          4
     v       v          |          |
    (B) -----8---------> (E) ------6-> (F) (tujuan)

Mari kita temukan jalur terpendek dari A ke semua simpul (dengan asumsi tidak ada F):

A:0, B:inf, C:inf, D:inf, E:inf

Proses:

Mulai dari A (jarak 0). PQ: [(0, A)]. Visited: {}.
Keluarkan A. Jarak A=0. Visited: {A}.
- Tetangga A: B (jarak=0+10=10), C (jarak=0+5=5).
Jarak: A:0, B:10, C:5. PQ: [(5,C), (10,B)].
Keluarkan C (jarak 5). Jarak C=5. Visited: {A, C}.
- Tetangga C: D (jarak=5+1=6), E (jarak=5+2=7).
Jarak: A:0, B:10, C:5, D:6, E:7. PQ: [(6,D), (7,E), (10,B)].
Keluarkan D (jarak 6). Jarak D=6. Visited: {A, C, D}.
- Tetangga D: E (jarak=6+4=10). (10 > 7, tidak update E).
Jarak: A:0, B:10, C:5, D:6, E:7. PQ: [(7,E), (10,B)].
Keluarkan E (jarak 7). Jarak E=7. Visited: {A, C, D, E}.
- Tetangga E: B (jarak=7+8=15). (15 > 10, tidak update B).
Jarak: A:0, B:10, C:5, D:6, E:7. PQ: [(10,B)].
Keluarkan B (jarak 10). Jarak B=10. Visited: {A, C, D, E, B}.
- Tetangga B: E (jarak=10+8=18). (18 > 7, tidak update E).
Jarak: A:0, B:10, C:5, D:6, E:7. PQ: [].

Jarak Terpendek dari A: A:0, B:10, C:5, D:6, E:7

4. Pseudocode Algoritma


FUNCTION Dijkstra(graph, start_node):
    distances = CREATE MAP/ARRAY, initialized to infinity for all nodes
    distances[start_node] = 0

    priority_queue = new MinHeap() // Mengurutkan berdasarkan jarak
    priority_queue.INSERT(start_node, 0) // (node, distance)

    visited = new Set()

    WHILE priority_queue IS NOT EMPTY:
        // Ambil node dengan jarak terpendek dari PQ
        current_distance, current_node = priority_queue.EXTRACT_MIN()

        IF current_node IS IN visited:
            CONTINUE // Lewati jika sudah diproses

        visited.ADD(current_node)

        // Jelajahi tetangga
        FOR EACH neighbor_node, weight OF current_node.ADJACENT_NODES:
            // Hitung jarak baru ke tetangga ini melalui current_node
            new_distance = current_distance + weight

            // Jika jarak baru lebih pendek dari yang sudah ada
            IF new_distance < distances[neighbor_node]:
                distances[neighbor_node] = new_distance
                priority_queue.INSERT(neighbor_node, new_distance)

    RETURN distances // Peta jarak terpendek dari start_node ke semua node

5. Kompleksitas Waktu & Ruang

Kompleksitas Waktu:
- Menggunakan Priority Queue (Min-Heap): $O(E \log V)$ atau $O(E + V \log V)$ tergantung implementasi heap.
  - $E$ adalah jumlah sisi (edges), $V$ adalah jumlah simpul (vertices).
  - Setiap sisi akan diproses sekali ($E$ kali), dan setiap operasi pada heap (insert/extract_min) membutuhkan $O(\log V)$ waktu.
- Menggunakan Array (tanpa Priority Queue, scan linier): $O(V^2)$ pada graf padat.
Kompleksitas Ruang: $O(V + E)$ untuk menyimpan graf (adjacency list), array jarak, dan priority queue.

6. Aplikasi

**Sistem Peta & GPS:** Menemukan rute terpendek antar lokasi (misalnya, Google Maps).
**Routing Jaringan:** Menemukan jalur data terpendek dalam jaringan komputer.
**Transportasi:** Optimasi rute pengiriman barang.
**Game Development:** Pathfinding untuk karakter game.
**Analisis Biologi Komputasi:** Menemukan jalur terpendek dalam jaringan biokimia.