Laporan Praktikum 10 Struktur Data | Algoritma Dijkstra

Pada pertemuan kali ini kita akan belajar tentang algoritma Dijkstra dalam python.

Algoritma Dijkstra adalah metode klasik yang digunakan untuk mencari jalur terpendek dari satu titik ke titik lainnya dalam sebuah graph berbobot positif. Algoritma ini sering kita temukan di google maps yang dapat mencari rute tercepat dari rumah ke berbagai tempat dengan kemacetan yang berbeda-beda.

Sebelum membuat program, kita melakukan instalasi library terlebih dahulu.

pip install networkx matplotlib;

Note: lakukan penginstalan library jika menggunakan selain google collab, contohnya menggunakan Vs code. Karena jika menggunakan google collab sudah otomatis terpasang.

oke ini adalah kode program dari algoritma dijkstra. Karena kode programnya panjang, maka penjelasan akan saya bagi.

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

def dijkstra_with_path(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

Explanation : Fungsi ‘dijkstra_with_path’ di atas digunakan untuk mencari jalur terpendek dari satu titik awal (start) ke semua titik lainnya dalam sebuah graph berbobot positif menggunakan algoritma dijkstra. Prosesnya diawali dengan menginisialisasi jarak semua titik menjadi tak hingga (inf), kecuali titik awal yang bernilai (0), serta menyiapkan antrean prioritas (queue) untuk memproses titik dengan bobot terkecil secara efisien. Di dalam perulangan, fungsi ini akan mengambil titik terdekat saat itu, mengevaluasi setiap titik tetangganya, dan melakukan pembaruan jika ditemukan rute baru yang lebih pendek (relaxation). Pada akhirnya, fungsi ini akan mengembalikan kamus distances yang berisi total jarak terpendek ke setiap titik dan kamus previous untuk melacak urutan rute atau silsilah jalur yang terbentuk.

# Rekonstruksi Jalur

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

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, seed=42)
  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()

Explanation : Dua fungsi di atas digunakan untuk memproses dan menampilkan hasil rute terpendek yang telah ditemukan. Fungsi ‘get_path’ berfungsi melakukan pelacakan balik (backtracking) menggunakan kamus previous mulai dari titik tujuan (target) hingga kembali ke titik awal, lalu menyusunnya menjadi sebuah urutan list rute yang utuh. Sementara itu, fungsi ‘visualize_graph’ menggunakan pustaka ‘networkx’ dan ‘matplotlib’ untuk membuat representasi visual dari graf tersebut, lengkap dengan titik, panah penunjuk arah, dan bobot jarak di setiap jalurnya. Jika sebuah rute hasil dari ‘get_path’ dimasukkan ke dalam fungsi visualisasi ini, program akan secara otomatis mewarnai dan menebalkan jalur terpendek tersebut dengan garis berwarna merah agar mudah diidentifikasi.

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

Explanation : Bagian kode program ini merupakan tahap eksekusi utama (main program) untuk menguji seluruh fungsi algoritma dijkstra yang sudah dibuat sebelumnya. Di sini, sebuah graf berarah dan berbobot didefinisikan dalam bentuk dictionary (graph), di mana titik ‘A’ diatur sebagai lokasi awal (start_node) dan titik ‘Z’ sebagai tujuan akhir (end_node). Program kemudian menjalankan fungsi ‘dijkstra_with_path’ untuk menghitung jarak terpendek, menyusun urutan rutenya lewat fungsi ‘get_path’, lalu mencetak hasilnya ke layar (yang akan menampilkan total jarak dan urutan jalurnya). Terakhir, fungsi ‘visualize_graph’ dipanggil untuk menampilkan struktur graf secara visual dalam bentuk diagram, di mana rute terpendek yang berhasil ditemukan dari ‘A’ ke ‘Z’ akan otomatis ditandai dengan garis tebal berwarna merah.

Hasilnya :

jarak dari A ke Z : 14 Jalur: A — B — D — E — Z

Modifikasi Graph agar memiliki siklus

untuk memodifikasi graph agar memiliki siklus, kita hanya perlu menambahkan isi node yang kita buat dalam graph agar terhubung dengan node sebelumnya

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} #menambahkan nilai 'A' agar 'Z' terhubung dengan 'A' 
}

Menambahkan simpul baru dan mengamati jalur terpendek

# Coding Dijkstra
# Menambahkan simpul baru dan mengamati jalur terpendek

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

def dijkstra_with_path(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

# Rekonstruksi Jalur

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

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, seed=42)
  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, 'F': 1},
    'B' : {'C': 1, 'D': 5},
    'C' : {'D': 8, 'E': 10},
    'D' : {'E': 2, 'Z': 6},
    'E' : {'Z': 3},
    'F' : {'Z': 2},
    'Z' : {'A': 7}
}

# Jalankan Dijkstra
start_node = 'A'
end_node ='Z'
distances, previous = dijkstra_with_path(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)

jarak dari A ke Z : 3 Jalur: A — F — Z

Analyst : Setelah menambahkan simpul baru, dapat dilihat bahwa jalur terpendek yang sebelumnya adalah (A-B-D-E-Z) dengan jarak A ke Z adalah 14 berubah menjadi (A-F-Z) dengan jarak A ke Z adalah 3.

Ganti tata letak menggunakan circular layout atau kamada kawai layout

# Mengganti tata letak graf

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

def dijkstra_with_path(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

# Rekonstruksi Jalur

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

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)
  pos = nx.kamada_kawai_layout(G, weight=None)
  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, 'F': 1},
    'B' : {'C': 1, 'D': 5},
    'C' : {'D': 8, 'E': 10},
    'D' : {'E': 2, 'Z': 6},
    'E' : {'Z': 3},
    'F' : {'Z': 2},
    'Z' : {'A': 7}
}

# Jalankan Dijkstra
start_node = 'A'
end_node ='Z'
distances, previous = dijkstra_with_path(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)

jarak dari A ke Z : 3 Jalur: A — F — Z

Kamada Kawai Layout

Circular Layout