Struktur Data: Algoritma Dijkstra

Algoritma Dijkstra yang dikembangkan oleh Edsger W. Dijkstra pada tahun 1956 dan pada tahun 1959 dipublikasikan secara resmi ini merupakan algoritma untuk mencari jalur terpendek. Algoritma ini dirancang untuk menemukan jalur terpendek dari satu simpul asal ke satu atau semua simpul lain dalam sebuah graf berbobot positif.

Ia berfungsi pada graf yang bobot sisinya non-negatif dan dapat digunakan untuk graf terarah maupun tak terarah. Algoritmenya menelusuri grafik secara berulang, menandai simpul yang telah dikunjungi, dan memperbarui jarak terpendeknya dari simpul awal.

Cara kerjanya:

1. Inisialisasi: Tetapkan jarak 0 untuk simpul awal dan tak terhingga untuk semua simpul lainnya.

2. Perulangan:

• Pilih simpul yang belum dikunjungi dengan jarak terpendek dari simpul awal.
• Tandai simpul yang dipilih sebagai telah dikunjungi.
• Untuk setiap tetangga yang belum dikunjungi dari node yang dipilih, perbarui jaraknya jika jalur melalui node yang dipilih lebih pendek dari jarak saat ini.

3. Penghentian: Ulangi langkah 2 hingga semua node yang dapat dijangkau telah dikunjungi.

LANGKAH PRAKTIKUM

Berikut langkah-langkah penggunaan algoritma dijkstra yang dilakuakn pada google colab.

1. Instalasi Library

Sebelum menjalankan program, terlebih dahulu dilakukan instalasi library eksternal yang dibutuhkan menggunakan perintah:

!pip install network matplotlib

Penjelasan:

networkx digunakan untuk memproses dan memvisualisasikan struktur graf (graph), seperti simpul dan sisi.

matplotlib digunakan untuk menampilkan visualisasi graf dalam bentuk gambar.

Output tersebut menunjukkan bahwa library network dan matplotlib sudah tersedia di sistem, sehingga tidak perlu diinstal ulang. Pip hanya memberi informasi bahwa semua dependensi yang dibutuhkan sudah terpenuhi (Requirement already satisfied).

2. Struktur Data Graf dan Algoritma

Menuliskan ulang algoritma dijkstra untuk menghitung jarak terpendek, serta menyimpan jalur yang dilalui. Penulisan ini berguna untuk menampilkan visualisasi rute secara utuh.

import network
import matplotlib.pyplot as plt

Penjelasan:

• network dimuat untuk mengakses fitur terkait graf.
• matplotlib.pyplot diimpor dengan alias plt untuk keperluan visualisasi.

Fungsi dijkstra_with_paths (graph, start)

Fungsi ini mengimplementasikan algoritma Dijkstra untuk mencari jarak terpendek dari simpul awal (start) ke semua simpul lain dalam graf berbobot.

• Inisialisasi:

Semua simpul diatur memiliki jarak awal infinity (tak hingga).

Simpul awal (start) diberi jarak 0.

Struktur previous digunakan untuk menyimpan simpul sebelumnya dalam jalur terpendek.

• Priority Queue (heapq):

Digunakan untuk mengambil simpul dengan jarak terpendek saat ini secara efisien.

• Perulangan utama:

Ambil simpul dengan jarak terkecil dari antrean.

Periksa semua tetangga simpul tersebut.

Jika ditemukan jalur yang lebih pendek, perbarui jaraknya dan simpan simpul sebelumnya.

• Return:

Mengembalikan dua dictionary yaitu:

1. distances: jarak terpendek dari simpul awal ke setiap simpul.
2. previous: jalur asal tiap simpul untuk merekonstruksi rute terpendek.

3. Fungsi untuk Merekonstruksi Jalur

Fungsi ini digunakan untuk mengembalikan jalur terpendek dari simpul awal ke simpul tujuan (end) berdasarkan data hasil algoritma Dijkstra.

Penjelasan:

• previous adalah dictionary yang menyimpan simpul sebelumnya dalam jalur terpendek, hasil dari fungsi dijkstra_with_paths.
• Fungsi memulai dari simpul akhir (end) dan menelusuri mundur ke simpul awal menggunakan previous.
• Setiap simpul ditambahkan ke depan list path menggunakan insert(0, …) agar urutan jalurnya benar, dari awal ke akhir.
• Proses terus dilakukan hingga mencapai simpul awal, yaitu saat end menjadi None.

4. Visualisasi dengan networkx dan matplotlib

Fungsi ini digunakan untuk memvisualisasikan graf berbobot dan jalur terpendek (jika ada) menggunakan library networkx dan matplotlib.

Penjelasan:

• Pembuatan graf terarah (DiGraph) menggunakan nx.DiGraph(). Setiap node dan bobot (weight) dari dictionary graph ditambahkan sebagai sisi (edge) dalam graf.
• Posisi dan tampilan node dengan:

spring_layout yang menghasilkan posisi simpul secara otomatis agar tampilan rapi.

Simpul (node) digambar dengan warna biru muda dan ukuran besar agar mudah dibaca.

• Label sisi ditampilkan menggunakan nx.draw_networkx_edge_labels, yang menunjukkan bobot antar simpul.
• Penyorotan jalur terpendek:

Jika parameter path diberikan, maka fungsi akan menyorot jalur terpendek dengan warna merah dan garis lebih tebal.

Jalur dibuat dari pasangan simpul berturut-turut menggunakan zip(path, path[1:]).

• Tampilan graf: visualisasi akhirnya ditampilkan menggunakan plt.show().

5. Implementasi

Komponen yang sebelumnya telah dibuat akan dijalankan dengan contoh graf berikut. Dengan ini dapat dilihat hasil jalur terpendek dan visualnya secara langsung.

• 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': {}
}

Penjelasan:

Graf didefinisikan dalam bentuk dictionary berarah dan berbobot, dengan setiap key mewakili simpul (node). Serta nilai berupa dictionary lain yang menunjukkan tetangga dan bobot sisi ke tetangga tersebut.

• Eksekusi Algoritma Dijkstra

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

Penjelasan:

Program memanggil fungsi dijkstra_with_paths() untuk menghitung jarak terpendek dari simpul ‘A’ ke semua simpul lainnya. Hasilnya adalah:

1. distances: jarak minimum dari A ke setiap simpul.
2. previous: simpul sebelumnya dalam jalur terpendek.

• Rekonstruksi Jalur Terpendek

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)}")

Penjelasan:

Fungsi get_path() digunakan untuk menyusun jalur dari simpul awal ke simpul tujuan berdasarkan previous. Output ditampilkan berupa:

1. Total jarak terpendek dari A ke Z.
2. Urutan simpul pada jalur tersebut, dipisahkan dengan ->.

• Visualisasi Graf dan Jalur

visualize_graph(graph, path=shortest_path)

Penjelasan:

Fungsi ini menampilkan struktur graf beserta bobotnya. Jalur terpendek yang ditemukan akan disorot dengan warna merah, memudahkan identifikasi secara visual.

6. Output

Penjelasan:

Gambar di atas merupakan hasil visualisasi graf berbobot berarah yang merepresentasikan jaringan simpul dan jalur antar simpul. Visualisasi ini menggunakan library networkx dan matplotlib.

• Simpul digambarkan sebagai lingkaran berwarna biru muda.
• Arah panah menunjukkan arah hubungan dari satu simpul ke simpul lainnya.
• Angka di sisi menunjukkan bobot (jarak) antar simpul.
• Garis merah menandai jalur terpendek dari simpul A ke Z, berdasarkan hasil perhitungan algoritma Dijkstra.

Hasil yang diperoleh:

jarak dari A ke Z: 14
Jalur: A->B->D->E->Z

PRAKTIKUM

1. Modifikasi graf agar memiliki siklus dan ulangi visualisasinya.
2. Tambahkan simpul baru dan lihat bagaimana jalur terpendek berubah.
3. Ganti tata letak graf dengan pos = nx.circular_layout(G) atau kamada_kawai_layout.

Modifikasi

1. Graf Awal

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': {}
}

2. Modifikasi Graf

2.1 Graf Setelah Dimodifikasi

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': {'A': 7},     
    'F': {'E': 1},     
}

2.2 Penjelasan Modifikasi

• Modifikasi graf agar memiliki siklus dilakukan pada baris ‘Z’: {‘A’: 7}, yang ada dalam graf. Ini membuat siklus dari A hingga Z dan kembali ke A lagi yang membentuk loop atau siklus.
• Tambahkan simpul baru dilakukan pada baris** **‘F’: {‘E’: 1}, yang terdapat dalam graf. Dengan menambahkan simpul F yang terhubung dengan E. Dapat juga digunakan untuk start atau end.

3. Implementasi Dijkstra dan Visualisasi

3.1 Fungsi Visualisasi Graf

def visualize_graph(graph, path=None, layout='circular'):
    G = nx.DiGraph()

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

    if layout == 'circular':
        pos = nx.circular_layout(G)
    elif layout == 'kamada':
        pos = nx.kamada_kawai_layout(G)
    else:
        pos = nx.spring_layout(G)

    edge_labels = nx.get_edge_attributes(G, 'weight')
    nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=1500, font_size=10, arrows=True)
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)

    if path:
        path_edges = list(zip(path, path[1:]))
        nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='blue', width=3)

    plt.title('Visualisasi Graf dengan Jalur Terpendek')
    plt.show()

3.1.1 Penambahan Parameter Layout

• Menambahkan parameter layout=’circular’ agar dapat memilih jenis tata letak graf. Terdapat tiga jenis layout yaitu:

a. circular_layout: simpul diletakkan melingkar.

b. kamada_kawai_layout: tata letak berbasis energi untuk visualisasi yang lebih seimbang.

c. spring_layout: tata letak seperti gaya pegas (default jika tidak disebutkan atau invalid).

3.1.2 Pemilihan Tata Letak Secara Dinamis

• Penggunaan if-elif-else untuk menentukan layout berdasarkan input parameter.
• Fungsi dapat diulang dengan layout berbeda tanpa mengubah isi fungsi.

3.1.3 Perubahan Warna Jalur Terpendek

• Sebelumnya warna jalur merah (red).
• Setelah modifikasi diganti dengan warna biru (blue).

3.1.4 Penungkatan Ketebalan Jalur Terpendek

• Sebelumnya width=2.
• Setelag modifikasi menjadi width=3, agar jalur lebih menonjol dan jelas terlihat.

3.1.5 Penambahan Panah Arah

• Menambah arrows=True pada nx.draw untuk menampikan arah dari setiap edge.
• Berguna untuk membantu memahami arah hubungan anatr simpul, terutama pada graf berarah (directed graph).

3.1.6 Penambahan Judul Visualisasi

• Menambahkan plt.title(‘Visualisasi Graf dengan Jalur Terpendek’).
• Membuat visualisasi lebih informatif dan sesuai untuk laoran atau presentasi.

3.1.7 Struktur Kode Lebih Modular dan Fleksibel

• Dengan struktur kode yang telah diberbarui dapat digunakan ulang untuk berbagai jenis graf tanpa mengubah banyak kode.

3.2. Dijkstra dan Pemanggilan Visualisasi

# 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)

# Output hasil
print(f"Jarak dari {start_node} ke {end_node}: {distances[end_node]}")
print(f"Jalur: {' -> '.join(shortest_path)}")

# Visualisasi dengan layout circular
visualize_graph(graph, path=shortest_path, layout='circular')

# Visualisasi dengan layout kamada
visualize_graph(graph, path=shortest_path, layout='kamada')

3.2.1 Implementasi Algoritma Dijkstra dan Rekonstruksi Jalur

• Pada bagian untuk menjalankan Dijikstra awal node dan akhirnya tetap sama dan tidak diganti walaupun telah ditambahkan simpul baru.
• Bagian rekonstruksi jalur dan Output hasil tidak ada perubahan.

3.2.2 Layout

Pemanggilan layout baru:

a. Kamada Layout

visualize_graph(graph, path=shortest_path, layout='circular')

b. Circular Layout

visualize_graph(graph, path=shortest_path, layout='kamada')

• Visualisasi setelah diperbarui mendukung pemilihan tata letak graf lewat parameter layout.
• Kelebihannya sendiri yaitu bisa membandingkan bentuk graf berdasarkan tata letak yang berbeda dan lebih fleksibel untuk analisis graf yang kompleks atau besar.

4. Hasil/Output

Setelah melakukan modifikasi pada graf awal dengan siklus (Z → A) dan simpul F, hasil jalur terpendeknya adalah sebagai berikut:

4.1 Circular Layout

Circular Layout

4.2 Kamada Layout

Kamada Layout

Penjelasan:

• Graf dengan jalur terpendek berwarna biru dengan jaraknya 14 yang melalui jalur A -> B -> D -> E -> Z.

Dijkstra adalah algoritma pencarian jalur terpendek dari satu simpul ke simpul lainnya dalam graf berbobot positif. Algoritma ini bekerja dengan memperbarui jarak terpendek secara bertahap sambil menandai simpul yang telah dikunjungi, hingga semua simpul yang dapat dijangkau diproses. Dijkstra hanya dapat digunakan jika semua bobot sisi bernilai non-negatif dan bisa diaplikasikan pada graf terarah maupun tak terarah. Proses inisialisasi, pemilihan simpul dengan jarak minimum, dan pembaruan jarak ke tetangga menjadi inti dari efisiensi pencarian jalur terpendek.

Github Praktikum:

[embed]Praktikum 12 · Rahma-dwi-kartika-sari/praktikumsemester2_strukturdata@0b81cc3 Contribute to Rahma-dwi-kartika-sari/praktikumsemester2_strukturdata development by creating an account on GitHub.github.com

Github Tugas:

[embed]praktikumsemester2_strukturdata/2410506008_Strukdat_Tugas_Dijikstra.ipynb at main ·… Contribute to Rahma-dwi-kartika-sari/praktikumsemester2_strukturdata development by creating an account on GitHub.github.com

REFERENSI

Wardhani, O., & Alfath, I. (2024/2025). Modul Praktikum Struktur Data: Dijkstra. Universitas Tidar.