Algoritma Dijkstra

Pendahuluan

Algoritma Dijkstra merupakan algoritma pencarian jalur terpendek yang dikembangkan oleh Edsger W. Dijkstra pada tahun 1956. Algoritma ini digunakan untuk menentukan jarak minimum dari satu simpul sumber ke simpul lainnya dalam sebuah graf berbobot positif.

Dijkstra bekerja dengan memilih simpul yang memiliki jarak terkecil yang belum dikunjungi, kemudian memperbarui jarak ke simpul-simpul tetangganya. Proses ini dilakukan berulang hingga seluruh simpul telah diproses.

Algoritma ini banyak digunakan dalam berbagai bidang, seperti sistem navigasi GPS, routing jaringan komputer, distribusi logistik, dan pengembangan game.

Tujuan

• Memahami konsep dan prinsip kerja Algoritma Dijkstra.
• Mengimplementasikan Algoritma Dijkstra menggunakan Python.
• Menentukan jalur terpendek pada graf berbobot positif.
• Memvisualisasikan graf dan jalur terpendek menggunakan library NetworkX dan Matplotlib.

Langkah

1. Instalasi Library

!pip install networkx matplotlib

• NetworkX digunakan untuk membuat dan mengelola struktur graf.
• Matplotlib digunakan untuk menampilkan visualisasi graf dalam bentuk gambar.

2. Struktur data Graf dan Algoritma

Graf direpresentasikan sebagai adjacency list menggunakan dictionary bersarang. Fungsi dijkstra_with_paths tidak hanya menghitung jarak terpendek, tetapi juga menyimpan simpul sebelumnya (previous) agar jalur bisa direkonstruksi.

import heapq
import networkx as nx
import matplotlib.pyplot as plt

def dijkstra_with_paths(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    previous = {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
                previous[neighbor] = current_node
                heapq.heappush(queue, (distance, neighbor))

    return distances, previous

• distances menyimpan jarak terpendek dari simpul asal ke setiap simpul lain, diinisialisasi dengan inf.
• previous menyimpan simpul sebelumnya di jalur terpendek, berguna untuk rekonstruksi jalur.
• heapq memastikan kita selalu memproses simpul dengan jarak terkecil terlebih dahulu (priority queue).

3. Fungsi untuk Merekonstruksi Jalur

Setelah algoritma selesai, kita perlu membangun kembali jalur yang ditempuh dari simpul asal ke simpul tujuan menggunakan dictionary previous.

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

Fungsi get_paths menelusuri mundur dari simpul tujuan ke simpul awal menggunakan dictionary previous, kemudian menghasilkan list yang merepresentasikan urutan simpul yang dilalui.

4. Visualisasi dengan NetworkX dan Matplotlib

Langkah ini menggambarkan graf dan menandai jalur terpendek menggunakan garis tebal berwarna merah.

def visualize_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)
    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()

Fungsi visualize_graph menggambar graf berdasarkan data input dan menandai jalur terpendek dengan warna merah. Ini membantu kita melihat secara visual bagaimana simpul dan jalur saling terhubung.

4. Penggunaan Lengkap

Terakhir, kita menjalankan seluruh komponen yang sudah dibuat dengan graf contoh dari simpul ‘A’ ke ‘Z’.

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

# Jalankan Dijkstra
start_node = 'A'
end_node = 'Z'
distances, previous = dijkstra_with_paths(graph, start_node)

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

# Visualisasi
visualize_graph(graph, path=shortest_path)

output

Graf divisualisasikan dengan jalur terpendek ditandai garis merah tebal.

Tugas

Soal 1. Modifikasi graf agar memiliki siklus

Kita menambahkan edge E -> B sehingga graf memiliki siklus, lalu melihat apakah jalur terpendek berubah.

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

distances, previous = dijkstra_with_paths(graph, 'A')
shortest_path = get_path(previous, 'Z')

print(f"Jarak: {distances['Z']}")
print(f"Jalur: {' -> '.join(shortest_path)}")

visualize_graph(graph, path=shortest_path)

output

Meskipun ada siklus, algoritma Dijkstra tetap menemukan jalur terpendek yang sama karena setiap bobot bernilai positif.

Soal 2. Tambahkan simpul baru

Kita menambahkan simpul baru F sebagai jalur alternatif menuju Z.

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

distances, previous = dijkstra_with_paths(graph, 'A')
shortest_path = get_path(previous, 'Z')

print(f"Jarak: {distances['Z']}")
print(f"Jalur: {' -> '.join(shortest_path)}")

visualize_graph(graph, path=shortest_path)

output

Dengan penambahan simpul F yang bobotnya lebih kecil, jalur terpendek berubah dan jaraknya menjadi lebih pendek dari sebelumnya (12 → 11).

Soal 3. Ganti tata letak graf (Layout)

Kita mengganti layout dari spring_layout menjadi circular_layout untuk tampilan yang berbeda.

def visualize_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.circular_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()

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

# Jalankan Dijkstra
start_node = 'A'
end_node = 'Z'
distances, previous = dijkstra_with_paths(graph, start_node)

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

# Visualisasi
visualize_graph(graph, path=shortest_path)

output

Dengan circular_layout, simpul-simpul disusun melingkar sehingga graf terlihat lebih rapi dan simetris.

Kesimpulan

Algoritma Dijkstra merupakan salah satu algoritma pencarian jalur terpendek yang paling efisien dan banyak digunakan. Dalam Python, implementasinya memanfaatkan priority queue (heapq) untuk efisiensi pemilihan simpul terkecil, dictionary sebagai adjacency list untuk representasi graf, serta networkx dan matplotlib untuk visualisasi.

Dari praktikum ini, kita belajar bahwa:

• Dijkstra hanya bekerja pada graf dengan bobot positif.
• Penambahan siklus tidak mempengaruhi kebenaran hasil selama semua bobot positif.
• Penambahan simpul baru dapat mengubah jalur terpendek jika bobotnya lebih kecil.
• Tampilan graf dapat dikustomisasi dengan berbagai layout yang disediakan oleh NetworkX.

[embed]Struktur-Data/Pertemuan-10/StrukurData_Pertemuan_10.ipynb at main · Aufanashr/Struktur-Data Contribute to Aufanashr/Struktur-Data development by creating an account on GitHub.github.com