Implementasi Algoritma Dijkstra Pada Python

img src: https://analyticsstepsfiles.s3.ap-south-1.amazonaws.com/backend/media/thumbnail/7400104/3067959_1607685601_Untitled-1%20(6).jpg

Hai semuanya! balik lagi sama aku Asfa. Pada pertemuan Praktikum Struktur Data kali ini aku mempelajari tentang Algoritma Dijkstra di python. Buat gambaran singkat Algoritma Dijkstra seperti google maps atau sistem navigasi, yang mencari jalur terpendek ke lokasi tujuan. Kalau kalian penasaran yuk ikut belajar juga!

Pengertian

Algoritma Dijkstra dikembangkan oleh Edsger W. Dijkstra, seorang ilmuwan komputer asal Belanda, pada tahun 1956 dan dipublikasikan secara resmi pada tahun 1959 . Motivasi awal pengembangan algoritma ini muncul dari kebutuhan untuk menentukan rute terpendek dalam sistem transportasi atau komunikasi dalam jaringan yang kompleks . Saat ini, algoritma Dijkstra menjadi dasar dalam teori graf dan banyak diaplikasikan pada:

• Sistem navigasi (contoh: Google Maps)
• Routing jaringan komputer
• Manajemen logistik dan distribusi barang
• Sistem game dan simulasi jalur

Secara definisi, algoritma Dijkstra adalah algoritma pencarian jalur terpendek dari satu simpul asal ke satu atau semua simpul lain dalam sebuah graf berbobot positif . Perlu diingat bahwa semua bobot sisi (edges) harus bernilai positif . Jika terdapat sisi dengan bobot negatif, algoritma ini tidak menjamin hasil yang benar, sehingga pendekatan lain seperti Bellman-Ford akan lebih cocok .

Implementasi dan Kompleksitas

Untuk mengimplementasikan Dijkstra menggunakan Python, kita bisa menggunakan struktur data dictionary bersarang sebagai representasi adjacency list dari graf . Struktur ini efisien dan sangat mudah dibaca .

Selain itu, agar efisiensi pencarian simpul minimum lebih optimal, kita menggunakan priority queue (antrian prioritas) dengan bantuan modul bawaan Python yaitu heapq . Dari segi kompleksitas waktu, penerapan heapq sangat penting! Jika algoritma ini dibuat secara iteratif biasa, kompleksitasnya mencapai O(V²), namun berkat heapq , kompleksitasnya dapat ditekan secara signifikan menjadi O((V + E) log V) di mana V adalah jumlah simpul dan E adalah jumlah sisi.

Langkah Praktikum

1. Instalasi Library

Untuk mendukung visualisasi graf dan jalur terpendek, kita memerlukan pustaka networkx untuk memanipulasi graf dan matplotlib untuk menampilkannya secara visual, untuk itu kita perlu menginstall nya terlebih dahulu

pip install networkx matplotlib

2. Struktur Data Graf dan Algoritma Dijkstra

Kita akan menyusun fungsi dijkstra_with_paths yang tidak hanya menghitung jarak terpendek, tetapi juga merekam jejak jalur simpul yang dilalui pada dictionary previous . Priority queue memastikan pemilihan simpul tercepat secara efisien .

def dijkastra_with_paths(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    prev = {node: None for node in graph}
    queue = [(0, start)]

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                prev[neighbor] = current_node
                heapq.heappush(queue, (distance, neighbor))

    return distances, prev

3. Fungsi untuk Merekonstruksi Jalur & Visualisasi

Kita perlu membangun fungsi get_path untuk menyusun ulang simpul dari dictionary previous menjadi list rute, serta fungsi visualize_graph untuk menggambarnya dan memberikan garis tebal berwarna merah untuk lintasan terpendek.

def get_path(prev, target):
    path = []
    while target is not None:
        path.insert(0, target)
        target = prev[target]
    return path

def visualisasi_graph(graph, path=None):
    G = nx.DiGraph()

    for node in graph:
        for neighbor, weight in graph[node].items():
            G.add_edge(node, neighbor, weight=weight)

    pos = nx.spring_layout(G)
    pos = nx.kamada_kawai_layout(G)
    edge_labels = nx.get_edge_attributes(G, 'weight')

    plt.figure(figsize=(8, 6))
    nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000, font_weight='bold', arrows=True)
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)

    # Garis tebal untuk jalur terpendek
    if path and len(path) > 1:
        path_edges = list(zip(path, path[1:]))
        nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='red', width=3)

    plt.title("Visualisasi Graf dan Jalur Terpendek")
    plt.axis('off')
    plt.show()

4. Penggunaan Lengkap

Mari kita jalankan dengan contoh graf yang telah disiapkan. Kita uji rute dari simpul ‘A’ ke ‘Z’ .

# Definisi graf
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'C': 1, 'D': 5},
    'C': {'D': 8, 'E': 10},
    'D': {'B': 2, 'Z': 6},
    'E': {'Z': 3},
    'Z': {}
}

# Menjalankan Dijkstra
start_node = 'A'
end_node = 'Z'
distance, prev = dijkastra_with_paths(graph, start_node)

# Rekonstruksi jalur
jalur_terpendek = get_path(prev, end_node)
print(f"""Jarak dari {start_node} ke {end_node} : {distance[end_node]}
Jalur: {'->'.join(jalur_terpendek)}
""")

Gambar 1. Jarak dan rute dari A ke Z.

visualisasi_graph(graph, path=jalur_terpendek

Gambar 2. Hasil visualisasi rute dan jarak.

Latihan dan Tugas

Pada akhir modul praktikum, terdapat beberapa latihan yang menantang pemahaman kita tentang graf:

1. Membuat Siklus: Menghubungkan simpul akhir 'Z' kembali ke simpul awal/sebelumnya ('A' bernilai bobot 7 dan 'C' bernilai bobot 3).

2. Membuat Simpul Baru: Menambahkan simpul baru yaitu simpul 'N' yang terhubung dari 'A' dan mengarah ke simpul 'B', 'E', dan 'Z'.

3. aksjhdja

# Definisi graf
graph = {
    'A' : {'B' : 4, 'C' : 2, 'N' : 2},
    'B' : {'C' : 1, 'D' : 5},
    'C' : {'D' : 8, 'E' : 10},
    'D' : {'E' : 2, 'Z' : 6},
    'E' : {'Z' : 3},
    'N' : {'B': 1, 'E' : 5, 'Z' : 6}, # 2. Membuat simpul baru
    'Z' : {'A' : 7, 'C' : 3} # 1. Membuat siklus
}

def get_path(prev, target):
    path = []
    while target is not None:
        path.insert(0, target)
        target = prev[target]
    return path

def visualisasi_graph(graph, path=None):
    G = nx.DiGraph()

    for node in graph:
        for neighbor, weight in graph[node].items():
            G.add_edge(node, neighbor, weight=weight)

    # pos = nx.spring_layout(G)
# 3. Membuat visualisasi dengan layout yang lain
    # pos = nx.circular_layout(G)
    pos = nx.kamada_kawai_layout(G)
    edge_labels = nx.get_edge_attributes(G, 'weight')

    plt.figure(figsize=(8, 6))
    nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000, font_weight='bold', arrows=True)
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)

    # Garis tebal untuk jalur terpendek
    if path and len(path) > 1:
        path_edges = list(zip(path, path[1:]))
        nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='red', width=3)

    plt.title("Visualisasi Graf dan Jalur Terpendek")
    plt.axis('off')
    plt.show()

# Menjalankan Dijkstra
start_node = 'A'
end_node = 'Z'
distance, prev = dijkastra_with_paths(graph, start_node)

# Rekonstruksi jalur
jalur_terpendek = get_path(prev, end_node)
print(f"""Jarak dari {start_node} ke {end_node} : {distance[end_node]}
Jalur: {'->'.join(jalur_terpendek)}
""")

Gambar 3. Hasil jarak dan rute dari A ke Z setelah ditambah simpul N dan memiliki siklus.

visualisasi_graph(graph, path=jalur_terpendek)

Gambar 4, Hasil visualisasi dengan circular layout.

Gambar 4, Hasil visualisasi dengan kamada kawai layout.

Analisis Jalur: Berdasarkan hasil eksekusi program di atas, pencarian rute terpendek dari simpul ‘A’ menuju simpul tujuan ‘Z’ menghasilkan total jarak akumulatif sebesar 8 dengan lintasan rute: A -> N -> Z. Meskipun graf ini memiliki struktur siklus (di mana 'Z' mengarah balik ke 'A' dan 'C'), algoritma Dijkstra tidak terjebak ke dalam looping tak terbatas karena adanya kondisi evaluasi jarak minimum yang ketat di dalam antrian prioritas (heapq). Selain itu, penambahan simpul baru 'N' dengan bobot langsung ke 'Z' sebesar 6 terbukti memangkas rute lama (yang sebelumnya harus memutar melewati simpul B, D, atau E) sehingga komputasi berhasil menemukan jalur pintas yang jauh lebih optimal.

Kesimpulan

Dari praktikum kali ini, kita bisa menyimpulkan bahwa algoritma Dijkstra sangat efisien dalam menyelesaikan permasalahan penentuan jalur terpendek pada graf berbobot positif. Melalui kombinasi dictionary dan antrian prioritas (heapq), Python dapat mengeksekusi perhitungan jarak secara cepat dengan kompleksitas yang rendah. Adanya siklus pada graf terarah tidak mengacaukan perhitungan selama seluruh bobot sisi bernilai positif. Ditambah lagi, pustaka networkx dan matplotlib sangat mempermudah kita untuk memvisualisasikan bagaimana simpul dan jalur tersebut saling terhubung secara spasial. Paham konsep teorinya dapet, visualisasinya juga kece!

Itu semua apa aja yang aku pelajari pada praktikum kali ini, tunggu di praktikum selanjutnya ya!

Referensi dan Lampiran

Sebagai bagian dari transparansi dan dokumentasi teknis, seluruh kode sumber yang digunakan dalam praktikum ini telah diunggah ke repositori GitHub. Hal ini juga bertujuan untuk memudahkan pengelolaan versi ( version control ) di masa mendatang.

• GitHub Repositori : https://github.com/asfadani/asfadani_kuliah.git
• File IPYNB : Praktikum 10 Struktur Data — Algoritma Dijkstra pada Python
• Referensi Utama : Olivia Wardhani, M.Eng , Ikhwan Alfath, M.Kom . Modul Praktikum Dijkstra Algorithm (Module 010) . Teknologi Informasi Universitas Tidar Magelang, 2024/2025

Disusun Oleh

Muhammad Fauza Asfadani (2505060011)

TIF25/R-01