Belajar Algoritm - Shortest Path Lanjut: Dijkstra, Bellman-Ford & Floyd-Warshall

#Pendahuluan

Setelah di episode 18 kita membahas BFS & DFS untuk shortest path unweighted, pada episode ini kita masuk ke masalah yang lebih realistis: shortest path di graph berbobot. Tiga algoritma utama — Dijkstra, Bellman-Ford, dan Floyd-Warshall — masing-masing menangani situasi yang berbeda: bobot non-negatif, bobot negatif, dan all-pairs.

Memahami kapan menggunakan algoritma mana adalah keterampilan inti: Dijkstra untuk single-source tercepat (jika tidak ada bobot negatif), Bellman-Ford untuk graph dengan bobot negatif dan deteksi siklus negatif, Floyd-Warshall untuk all-pairs pada graph kecil.

#Dijkstra's Algorithm

Dijkstra menemukan shortest path dari satu source ke semua vertex dalam graph dengan bobot non-negatif. Menggunakan priority queue (min-heap) untuk memproses vertex dengan jarak terpendek terlebih dahulu.

import heapq
 
def dijkstra(graph, source, n):
    """graph: adjacency list [(to, weight)]"""
    dist = [float('inf')] * n
    dist[source] = 0
    prev = [-1] * n
    pq = [(0, source)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(pq, (dist[v], v))
    
    return dist, prev
 
def reconstruct_path(prev, target):
    path = []
    while target != -1:
        path.append(target)
        target = prev[target]
    return list(reversed(path))

#Kompleksitas

#Bellman-Ford

Bellman-Ford menemukan shortest path dari satu source ke semua vertex — termasuk graph dengan bobot negatif. Berbasis DP: lakukan V-1 iterasi relaksasi pada semua edge.

def bellman_ford(edges, source, n):
    """edges: [(u, v, weight)]"""
    dist = [float('inf')] * n
    dist[source] = 0
    
    # V-1 iterasi relaksasi
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # Deteksi siklus negatif (iterasi ke-V)
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # ada siklus negatif
    
    return dist

#Mengapa V-1 Iterasi?

Shortest path tanpa siklus memiliki maksimal V-1 edge. Setiap iterasi menjamin shortest path dengan satu edge lebih banyak ditemukan. Iterasi ke-V mendeteksi siklus negatif — jika masih ada relaksasi, berarti ada siklus yang bisa di-loop untuk mengurangi jarak tanpa batas.

#Kompleksitas

#Floyd-Warshall

Floyd-Warshall menemukan shortest path antara semua pasang vertex — all-pairs shortest path. Menggunakan DP 3D: dp[k][i][j] = shortest path dari i ke j menggunakan vertex 0..k sebagai perantara.

def floyd_warshall(n, edges):
    # Inisialisasi
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)
    
    # DP: tambahkan vertex k sebagai perantara
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

#Kompleksitas

Deteksi siklus negatif: jika dist[i][i] < 0 untuk vertex i, ada siklus negatif yang melibatkan i.

#Perbandingan Ketiga Algoritma

#Praktik

Implementasi Floyd-Warshall pada graph kecil (5-10 vertex) — cetak matriks shortest path. Verifikasi dengan Dijkstra dari setiap vertex. Deteksi siklus negatif jika ada.

#Penutup

Pada episode 19 ini, kalian telah memahami:

• Dijkstra: O((V+E) log V) dengan priority queue — tercepat untuk bobot non-negatif.
• Bellman-Ford: O(VE) dengan V-1 iterasi — menangani bobot negatif + deteksi siklus negatif.
• Floyd-Warshall: O(V³) — all-pairs shortest path, cocok untuk graph kecil/dense.
• Pilihan algoritma bergantung pada: single vs all-pairs, ada bobot negatif atau tidak, ukuran graph.

Di episode 20 selanjutnya kita akan membahas Union-Find & Kruskal's MST — struktur data Union-Find dengan path compression dan Kruskal's algorithm untuk Minimum Spanning Tree. Sampai jumpa di episode 20!