Belajar Data Structure - Shortest Path (Dijkstra & Bellman-Ford)

#Pendahuluan

Setelah di episode 17 kita memahami topological sort dan cycle detection, pada episode ini kita mempelajari shortest path — dua algoritma yang menjawab pertanyaan: "Jalur mana dari A ke B yang total bobotnya paling kecil?" Dijkstra dan Bellman-Ford adalah dua solusi fundamental untuk masalah ini, masing-masing dengan trade-off yang berbeda.

Dijkstra lebih cepat tetapi tidak bisa menangani edge negatif. Bellman-Ford lebih lambat tetapi bisa menangani edge negatif dan mendeteksi negative cycle. Pemilihan antara keduanya tergantung pada sifat graph yang kalian hadapi.

#Dijkstra's Algorithm

#Konsep

Dijkstra menggunakan pendekatan greedy: dari semua node yang belum dikunjungi, pilih yang memiliki jarak terpendek dari source. Menggunakan priority queue (binary heap) untuk efisiensi.

#Implementasi

Dijkstra's algorithm

import heapq
 
def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    previous = {node: None for node in graph}
 
    while pq:
        current_dist, current_node = heapq.heappop(pq)
 
        if current_dist > distances[current_node]:
            continue
 
        for neighbor, weight in graph[current_node]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = current_node
                heapq.heappush(pq, (distance, neighbor))
 
    return distances, previous

#Kompleksitas

• O((V + E) log V) dengan binary heap
• Tidak boleh ada edge negatif — Dijkstra salah jika ada edge negatif

#Bellman-Ford Algorithm

#Konsep

Bellman-Ford menggunakan dynamic programming: relaksasi semua edge sebanyak V-1 kali. Jika setelah V-1 kali masih ada yang berkurang, berarti ada negative cycle.

#Implementasi

Bellman-Ford algorithm

def bellman_ford(edges, num_nodes, start):
    distances = [float('inf')] * num_nodes
    distances[start] = 0
 
    for _ in range(num_nodes - 1):
        for u, v, weight in edges:
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
 
    for u, v, weight in edges:
        if distances[u] + weight < distances[v]:
            return None  # Negative cycle terdeteksi
 
    return distances

#Kompleksitas

• O(VE) — lebih lambat dari Dijkstra
• Bisa menangani edge negatif
• Mendeteksi negative cycle

#Edge Negatif dan Negative Cycle

Edge negatif: bobot < 0. Negative cycle: cycle dengan total bobot negatif → bisa loop tanpa hingga untuk mengurangi jarak. Bellman-Ford mendeteksinya karena jarak masih berkurang setelah V-1 kali relaksasi.

#Perbandingan Dijkstra vs Bellman-Ford

#Praktik: Dijkstra pada Road Network

Dijkstra road network

graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8)],
    'D': [('B', 5), ('C', 8)]
}
 
distances, previous = dijkstra(graph, 'A')
print("Distances from A:", distances)

#Bellman-Ford pada Graph dengan Edge Negatif

Bellman-Ford dengan edge negatif

edges = [
    (0, 1, 4), (0, 2, 2), (1, 2, -1),
    (1, 3, 5), (2, 3, 8)
]
distances = bellman_ford(edges, 4, 0)
print("Bellman-Ford distances:", distances)

#Aplikasi

• GPS navigation: mencari rute tercepat
• Routing protocol: OSPF, RIP
• Currency arbitrage: deteksi negative cycle dalam graf nilai tukar
• Game pathfinding: AI mencari jalur terpendek

#Penutup

Inti yang harus dibawa pulang:

• Dijkstra: greedy + priority queue, O((V+E) log V), tidak boleh edge negatif.
• Bellman-Ford: dynamic programming, O(VE), bisa edge negatif + deteksi negative cycle.
• Negative cycle = total bobot cycle < 0 → jarak bisa berkurang tanpa henti.
• Pilih Dijkstra untuk graph non-negatif, Bellman-Ford untuk graph dengan edge negatif.
• Aplikasi: GPS, routing protocol, currency arbitrage.

Di episode 19 selanjutnya kita akan membahas Minimum Spanning Tree (Kruskal & Prim) — dua algoritma untuk menemukan subset edge dengan total bobot minimum yang menghubungkan semua node. Kruskal menggunakan Union-Find (yang akan kita pelajari mendalam di episode 20), Prim menggunakan priority queue. Pastikan kalian sudah paham edge weighting karena MST beroperasi pada weighted undirected graph!