Jalur terpendek dengan Dijkstra

Pada graf tanpa bobot, BFS menemukan jalur dengan sisi paling sedikit. Jika sisi punya bobot, misalnya jarak atau waktu tempuh, dibutuhkan algoritma Dijkstra.

Idenya

1. 1Jarak simpul awal 0, simpul lain tak hingga.
2. 2Ambil simpul yang belum selesai dengan jarak sementara terkecil. Jaraknya sekarang pasti final.
3. 3Relaksasi: untuk setiap tetangga, jika lewat simpul ini lebih pendek, perbarui jarak tetangga itu.
4. 4Ulangi sampai semua simpul selesai.

Heap dipakai untuk mengambil simpul berjarak terkecil dengan cepat.

1import heapq23def dijkstra(graf, awal):4    jarak = {s: float("inf") for s in graf}5    induk = {awal: None}6    jarak[awal] = 07    heap = [(0, awal)]8    while heap:9        d, u = heapq.heappop(heap)10        if d > jarak[u]:11            continue12        for v, bobot in graf[u]:13            if d + bobot < jarak[v]:14                jarak[v] = d + bobot15                induk[v] = u16                heapq.heappush(heap, (jarak[v], v))17    return jarak, induk1819def jalur(induk, tujuan):20    hasil = []21    while tujuan is not None:22        hasil.append(tujuan)23        tujuan = induk[tujuan]24    return hasil[::-1]2526graf = {27    "A": [("B", 4), ("C", 1)],28    "B": [("A", 4), ("C", 2), ("D", 5)],29    "C": [("A", 1), ("B", 2), ("D", 8), ("E", 10)],30    "D": [("B", 5), ("C", 8), ("E", 2)],31    "E": [("C", 10), ("D", 2)],32}33jarak, induk = dijkstra(graf, "A")34for s in sorted(jarak):35    print(f"A ke {s}: {jarak[s]:>2}  lewat {' -> '.join(jalur(induk, s))}")

A ke A:  0  lewat A
A ke B:  3  lewat A -> C -> B
A ke C:  1  lewat A -> C
A ke D:  8  lewat A -> C -> B -> D
A ke E: 10  lewat A -> C -> B -> D -> E

Jalur langsung A ke B berbobot 4, tetapi lewat C hanya 1 + 2 = 3. Baris if d > jarak[u]: continue melewati entri heap yang sudah usang.

Kompleksitas dan syarat

• Dengan binary heap: O((V + E) log V).
• Dijkstra adalah algoritma greedy: begitu sebuah simpul diambil dari heap, jaraknya dianggap final.
• Karena itu Dijkstra hanya benar untuk bobot tidak negatif. Sisi berbobot negatif bisa membuat jalur yang lebih pendek ditemukan belakangan. Untuk graf dengan bobot negatif, dipakai algoritma Bellman-Ford yang O(VE).

1import heapq23sisi = [("P", "Q", 7), ("P", "R", 9), ("P", "U", 14), ("Q", "R", 10), ("Q", "S", 15),4        ("R", "S", 11), ("R", "U", 2), ("S", "T", 6), ("U", "T", 9)]5graf = {}6for u, v, w in sisi:7    graf.setdefault(u, []).append((v, w))8    graf.setdefault(v, []).append((u, w))910jarak = {s: float("inf") for s in graf}11induk = {"P": None}12jarak["P"] = 013heap = [(0, "P")]14while heap:15    d, u = heapq.heappop(heap)16    if d > jarak[u]:17        continue18    for v, w in graf[u]:19        if d + w < jarak[v]:20            jarak[v] = d + w21            induk[v] = u22            heapq.heappush(heap, (jarak[v], v))2324rute = []25s = "T"26while s is not None:27    rute.append(s)28    s = induk[s]29print(jarak["T"], "menit lewat", " -> ".join(reversed(rute)))

20 menit lewat P -> R -> U -> T