Menerapkan Algoritma Dijkstra di Python: Tutorial Langkah demi Langkah

Mengapa Perlu Mempelajari Algoritma Dijkstra?

Dijkstra adalah algoritma andalan untuk menemukan jalur terpendek antara dua titik dalam sebuah jaringan, dengan banyak penerapan. Ini adalah dasar dalam ilmu komputer dan teori graf. Memahaminya dan belajar menerapkannya membuka pintu ke algoritma graf yang lebih lanjut dan berbagai aplikasinya.

Algoritma ini juga mengajarkan pendekatan pemecahan masalah yang berharga melalui algoritma rakus (greedy), yang melibatkan pengambilan pilihan optimal di setiap langkah berdasarkan informasi saat ini.

Keterampilan ini dapat ditransfer ke algoritma optimasi lainnya. Algoritma Dijkstra mungkin bukan yang paling efisien di semua skenario, tetapi bisa menjadi tolok ukur yang baik saat menyelesaikan masalah “jarak terpendek”.

Contohnya meliputi:

• Sistem navigasi GPS yang mencari rute tercepat
• Perutean paket data dalam jaringan komputer
• Layanan pengiriman yang mengoptimalkan rute agar efisien
• Jejaring sosial (menyarankan koneksi)
• Keuangan (mencari jalur investasi optimal)
• Manajemen proyek (mencari alur kerja paling efisien)

Bahkan jika Anda tidak tertarik pada hal-hal tersebut, menerapkan algoritma Dijkstra di Python akan memungkinkan Anda berlatih konsep penting seperti:

• Kelas (class) Python
• Dictionary comprehension
• List comprehension
• Priority queue

Konsep Kunci Terkait Graf

Untuk menerapkan algoritma Dijkstra di Python, kita perlu menyegarkan beberapa konsep esensial dari teori graf. Pertama-tama, ada graf itu sendiri:

Graf adalah kumpulan node (simpul/vertex) yang dihubungkan oleh edge (sisi). Node merepresentasikan entitas atau titik dalam jaringan, sedangkan edge merepresentasikan koneksi atau hubungan di antara keduanya.

Graf bisa berbobot atau tidak berbobot. Pada graf tidak berbobot, semua edge memiliki bobot yang sama (sering disetel ke 1). Pada graf berbobot (seperti yang Anda duga), setiap edge memiliki bobot yang terkait, sering kali merepresentasikan biaya, jarak, atau waktu.

Kita akan menggunakan graf berbobot dalam tutorial ini karena diperlukan untuk algoritma Dijkstra.

Sebuah jalur dalam graf mengacu pada urutan node yang terhubung oleh edge, dimulai dan diakhiri pada node tertentu. Jalur terpendek, yang menjadi fokus kita di tutorial ini, adalah jalur dengan total bobot minimum (jarak, biaya, dan sebagainya).

Algoritma Dijkstra Dijelaskan secara Visual

Untuk sisa tutorial, kita akan menggunakan graf terakhir yang kita lihat:

Mari kita coba menemukan jalur terpendek antara titik B dan F menggunakan algoritma Dijkstra dari setidaknya tujuh jalur yang mungkin. Awalnya, kita akan mengerjakannya secara visual dan nanti mengimplementasikannya dalam kode.

Pertama, kita inisialisasi algoritma sebagai berikut:

1. Kita tetapkan B sebagai node akar (sumber).
2. Kita tetapkan jarak antara B dan semua node lainnya menjadi tak hingga sebagai nilai jarak sementara awal. Kita tetapkan nilai untuk B menjadi 0 karena itu jarak ke dirinya sendiri:

Lalu, kita jalankan langkah-langkah berikut secara iteratif:

1. Pilih node dengan nilai terkecil sebagai “node saat ini” dan kunjungi semua node tetangganya. Saat kita mengunjungi setiap tetangga, kita perbarui nilai sementaranya dari tak hingga menjadi bobot edge mereka mulai dari node sumber.
2. Setelah semua tetangga dari node saat ini dikunjungi, kita tandai node saat ini sebagai “sudah dikunjungi.” Setelah sebuah node ditandai “sudah dikunjungi,” nilainya sudah merupakan jalur terpendek dari target.
3. Algoritma kembali ke langkah 1 dan memilih node dengan nilai terkecil.

Dalam graf kita, B memiliki tiga tetangga — A, D, dan E. Mari kita kunjungi masing-masing mulai dari node akar dan perbarui nilainya (iterasi 1) berdasarkan bobot edge-nya:

Pada iterasi 2, kita kembali memilih node dengan nilai terkecil, kali ini — E. Tetangganya adalah C, D, dan G. B dikecualikan karena sudah kita kunjungi. Mari perbarui nilai tetangga E:

Kita set nilai C menjadi 5,6 karena nilainya adalah jumlah kumulatif bobot dari B ke C. Hal yang sama berlaku untuk G. Namun, jika Anda perhatikan, nilai D tetap 3,5 padahal seharusnya 3,5 + 2,8 = 6,3, seperti pada node lainnya.

Aturannya adalah jika jumlah kumulatif yang baru lebih besar daripada nilai saat ini pada node tersebut, kita tidak akan memperbaruinya karena node itu sudah mencatat jarak terpendek ke akar. Dalam kasus ini, nilai D saat ini sebesar 3,5 sudah menunjukkan jarak terpendek ke B karena mereka adalah tetangga.

Kita lanjutkan dengan cara ini hingga semua node dikunjungi. Ketika akhirnya terjadi, kita akan memiliki jarak terpendek ke setiap node dari B dan kita bisa langsung melihat nilai dari B ke F.

Singkatnya, langkah-langkahnya adalah:

1. Inisialisasi graf dengan node sumber bernilai 0 dan semua node lainnya tak hingga. Mulai dengan sumber sebagai “node saat ini”.
2. Kunjungi semua node tetangga dari node saat ini dan perbarui nilainya menjadi jumlah kumulatif bobot (jarak) dari sumber. Jika nilai saat ini tetangga lebih kecil daripada jumlah kumulatif, biarkan tetap. Tandai “node saat ini” sebagai selesai.
3. Tandai node bernilai minimum yang belum selesai sebagai “node saat ini”.
4. Ulangi langkah 2 dan 3 hingga semua node selesai.

Implementasi Langkah demi Langkah Algoritma Dijkstra di Python

Sekarang, untuk menguatkan pemahaman Anda tentang algoritma Dijkstra, kita akan belajar menerapkannya di Python langkah demi langkah.

Memahami graf sebagai dictionary

Pertama, kita butuh cara merepresentasikan graf di Python — opsi paling populer adalah menggunakan dictionary. Jika ini adalah graf kita:

Kita bisa merepresentasikannya dengan dictionary berikut:

graph = {
   "A": {"B": 3, "C": 3},
   "B": {"A": 3, "D": 3.5, "E": 2.8},
   "C": {"A": 3, "E": 2.8, "F": 3.5},
   "D": {"B": 3.5, "E": 3.1, "G": 10},
   "E": {"B": 2.8, "C": 2.8, "D": 3.1, "G": 7},
   "F": {"G": 2.5, "C": 3.5},
   "G": {"F": 2.5, "E": 7, "D": 10},
}
Didukung oleh

Setiap key pada dictionary adalah sebuah node dan setiap value adalah dictionary yang berisi tetangga dari key tersebut dan jarak ke sana. Graf kita memiliki tujuh node yang berarti dictionary harus memiliki tujuh key.

Sumber lain sering menyebut dictionary di atas sebagai adjacency list dictionary. Kita akan berpegang pada istilah itu mulai sekarang.

1. Membuat kelas Graph

Untuk membuat kode lebih modular dan mudah diikuti, kita akan menerapkan kelas Graph sederhana untuk merepresentasikan graf. Di balik layar, kelas ini akan menggunakan adjacency list dictionary. Kelas ini juga akan memiliki metode untuk dengan mudah menambahkan koneksi antara dua node:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph  # A dictionary for the adjacency list

   def add_edge(self, node1, node2, weight):
       if node1 not in self.graph:  # Check if the node is already added
           self.graph[node1] = {}  # If not, create the node
       self.graph[node1][node2] = weight  # Else, add a connection to its neighbor
Didukung oleh

Dengan menggunakan kelas ini, kita dapat membangun graf kita secara iteratif dari awal seperti ini:

G = Graph()

# Add A and its neighbors
G.add_edge("A", "B", 3)
G.add_edge("A", "C", 3)

# Add B and its neighbors
G.add_edge("B", "A", 3)
G.add_edge("B", "D", 3.5)
G.add_edge("B", "E", 2.8)

...
Didukung oleh

Atau kita bisa langsung mengoper adjacency list dictionary, yang lebih cepat:

# Use the dictionary we defined earlier
G = Graph(graph=graph)

G.graph
Didukung oleh

{'A': {'B': 3, 'C': 3},
'B': {'A': 3, 'D': 3.5, 'E': 2.8},
'C': {'A': 3, 'E': 2.8, 'F': 3.5},
'D': {'B': 3.5, 'E': 3.1, 'G': 10},
'E': {'B': 2.8, 'C': 2.8, 'D': 3.1, 'G': 7},
'F': {'G': 2.5, 'C': 3.5},
'G': {'F': 2.5, 'E': 7, 'D': 10}}
Didukung oleh

2. Menggunakan dictionary untuk menyimpan jarak dari sumber

Kita membuat metode kelas lain — kali ini untuk algoritmanya sendiri — shortest_distances:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   # The add_edge method omitted for space

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       ...
Didukung oleh

Hal pertama yang kita lakukan di dalam metode ini adalah mendefinisikan dictionary yang berisi pasangan node-nilai. Dictionary ini diperbarui setiap kali kita mengunjungi sebuah node dan tetangganya. Seperti yang disebutkan dalam penjelasan visual algoritma, nilai awal semua node diatur ke tak hingga sementara nilai sumber adalah 0.

Ketika kita selesai menulis metode ini, dictionary tersebut akan dikembalikan, dan ia akan berisi jarak terpendek ke semua node dari sumber. Kita akan bisa menemukan jarak dari B ke F seperti ini:

# Sneak-peek - find the shortest paths from B
distances = G.shortest_distances("B")

to_F = distances["F"]
print(f"The shortest distance from B to F is {to_F}")
Didukung oleh

3. Menggunakan priority queue untuk mengiterasi node

Sekarang, kita perlu cara untuk melakukan loop atas node graf sesuai aturan algoritma Dijkstra. Jika Anda ingat, pada setiap iterasi, kita perlu memilih node dengan nilai terkecil dan mengunjungi tetangganya.

Anda mungkin mengatakan bahwa kita bisa langsung melakukan loop atas key dictionary:

for node in graph.keys():
   ...
Didukung oleh

Metode ini tidak berhasil karena tidak memberi kita cara untuk mengurutkan node berdasarkan nilainya. Jadi, array sederhana tidak akan cukup. Untuk menyelesaikan bagian masalah ini, kita akan menggunakan sesuatu yang disebut priority queue.

Priority queue mirip seperti daftar (array) biasa, tetapi setiap elemennya memiliki nilai tambahan untuk merepresentasikan prioritasnya. Berikut contoh priority queue:

pq = [(3, "A"), (1, "C"), (7, "D")]Didukung oleh

Queue ini berisi tiga elemen — A, C, dan D — dan masing-masing memiliki nilai prioritas yang menentukan bagaimana operasi dilakukan pada queue. Python menyediakan pustaka built-in heapq untuk bekerja dengan priority queue:

from heapq import heapify, heappop, heappushDidukung oleh

Pustaka ini memiliki tiga fungsi yang kita butuhkan:

• heapify: Mengubah daftar tuple berisi pasangan prioritas-nilai menjadi priority queue.
• heappush: Menambahkan elemen ke queue dengan prioritas terkait.
• heappop: Menghapus dan mengembalikan elemen dengan prioritas tertinggi (elemen dengan nilai terkecil).

pq = [(3, "A"), (1, "C"), (7, "D")]

# Convert into a queue object
heapify(pq)

# Return the highest priority value
heappop(pq)
Didukung oleh

(1, 'C')Didukung oleh

Seperti yang Anda lihat, setelah kita mengonversi pq menjadi queue menggunakan heapify, kita bisa mengekstrak C berdasarkan prioritasnya. Mari coba mendorong (push) sebuah nilai:

heappush(pq, (0, "B"))

heappop(pq)
Didukung oleh

(0, 'B')Didukung oleh

Queue diperbarui dengan benar berdasarkan prioritas elemen baru karena heappop mengembalikan elemen baru dengan prioritas 0.

Perhatikan bahwa setelah kita pop sebuah item, item tersebut tidak lagi menjadi bagian dari queue.

Sekarang, kembali ke algoritma kita, setelah kita menginisialisasi distances, kita membuat priority queue baru yang awalnya hanya berisi node sumber:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       # Initialize a priority queue
       pq = [(0, source)]
       heapify(pq)

       # Create a set to hold visited nodes
       visited = set()
Didukung oleh

Prioritas setiap elemen di dalam pq adalah nilai saat ini. Kita juga menginisialisasi sebuah himpunan kosong untuk mencatat node yang sudah dikunjungi.

4. Algoritma Dijkstra sebagai loop while

Sekarang, kita mulai mengiterasi semua node yang belum dikunjungi menggunakan loop while:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       # Initialize a priority queue
       pq = [(0, source)]
       heapify(pq)

       # Create a set to hold visited nodes
       visited = set()

       while pq:  # While the priority queue isn't empty
           current_distance, current_node = heappop(
               pq
           )  # Get the node with the min distance

           if current_node in visited:
               continue  # Skip already visited nodes
           visited.add(current_node)  # Else, add the node to visited set
Didukung oleh

Selama priority queue tidak kosong, kita terus mem-pop node prioritas tertinggi (dengan nilai minimum) dan mengekstrak nilainya dan namanya ke current_distance dan current_node. Jika current_node ada di dalam visited, kita lewati. Jika tidak, kita tandai sebagai sudah dikunjungi dan kemudian lanjut mengunjungi tetangganya:

while pq:  # While the priority queue isn't empty
   current_distance, current_node = heappop(pq)

   if current_node in visited:
       continue 
   visited.add(current_node)

   for neighbor, weight in self.graph[current_node].items():
       # Calculate the distance from current_node to the neighbor
       tentative_distance = current_distance + weight
       if tentative_distance < distances[neighbor]:
           distances[neighbor] = tentative_distance
           heappush(pq, (tentative_distance, neighbor))

return distances
Didukung oleh

Untuk setiap tetangga, kita hitung jarak sementara dari node saat ini dengan menambahkan nilai saat ini tetangga ke bobot edge penghubung. Lalu, kita periksa apakah jarak tersebut lebih kecil dibandingkan jarak tetangga di distances. Jika ya, kita perbarui dictionary distances dan tambahkan tetangga beserta jarak sementaranya ke priority queue.

Selesai! Kita telah menerapkan algoritma Dijkstra. Mari kita uji:

G = Graph(graph)

distances = G.shortest_distances("B")
print(distances, "\n")

to_F = distances["F"]
print(f"The shortest distance from B to F is {to_F}")
Didukung oleh

{'A': 3, 'B': 0, 'C': 5.6, 'D': 3.5, 'E': 2.8, 'F': 9.1, 'G': 9.8}

The shortest distance from B to F is 9.1
Didukung oleh

Jadi, jarak dari B ke F adalah 9,1. Tapi tunggu: jalur yang mana?

5. Menyusun jalur terpendek

Saat ini, kita hanya memiliki jarak terpendek, bukan jalurnya, yang membuat graf kita terlihat seperti ini:

Untuk menyusun jalur terpendek dari jarak terpendek yang dihitung, kita bisa menelusuri balik langkah-langkah dari target. Untuk setiap edge yang terhubung ke F, kita kurangkan bobotnya:

1. 9,1–3,5 = 5,6
2. 9,1–2,5 = 6,5

Lalu, kita lihat apakah ada hasil yang cocok dengan nilai milik tetangga F. Hanya 5,6 yang cocok dengan nilai C, yang berarti C adalah bagian dari jalur terpendek.

Kita ulangi proses ini lagi untuk tetangga C yakni A dan E:

1. 5,6–3 = 2,6
2. 5,6–2,8 = 2,8

Karena 2,8 cocok dengan nilai E, maka E adalah bagian dari jalur terpendek. E juga tetangga B, yang membuat jalur terpendek antara B dan F — BECF.

Mari kita tambahkan implementasi proses ini ke kelas kita. Kodenya sedikit berbeda dari penjelasan di atas karena ia menemukan jalur terpendek antara B dan semua node lainnya, bukan hanya F.

Selain itu, prosesnya dilakukan secara terbalik, tetapi idenya sama.

Tambahkan baris-baris kode berikut ke akhir metode shortest_distances dengan menghapus pernyataan return lama:

predecessors = {node: None for node in self.graph}

for node, distance in distances.items():
   for neighbor, weight in self.graph[node].items():
       if distances[neighbor] == distance + weight:
           predecessors[neighbor] = node

return distances, predecessors
Didukung oleh

Saat kode dijalankan, dictionary predecessors berisi induk langsung dari setiap node yang terlibat dalam jalur terpendek ke sumber. Mari kita coba:

G = Graph(graph)

distances, predecessors = G.shortest_distances("B")

print(predecessors)
Didukung oleh

{'A': 'B', 'B': None, 'C': 'E', 'D': 'B', 'E': 'B', 'F': 'C', 'G': 'E'}Didukung oleh

Pertama, mari kita temukan jalur terpendek secara manual menggunakan dictionary predecessors dengan menelusuri balik dari F:

# Check the predecessor of F
predecessors["F"]
Didukung oleh

'C'  # It is CDidukung oleh

# Check the predecessor of C
predecessors["C"]
Didukung oleh

'E'  # It is EDidukung oleh

# Check the predecessor of E
predecessors["E"]
Didukung oleh

'B'  # It is BDidukung oleh

Nah, tepat! Dictionary tersebut dengan benar memberi tahu kita bahwa jalur terpendek antara B dan F adalah BECF.

Tetapi kita menemukannya secara semi-manual. Kita menginginkan sebuah metode yang secara otomatis mengembalikan jalur terpendek yang disusun dari dictionary predecessors dari sumber mana pun ke target mana pun. Kita definisikan metode ini sebagai shortest_path (tambahkan di akhir kelas):

def shortest_path(self, source: str, target: str):
   # Generate the predecessors dict
   _, predecessors = self.shortest_distances(source)

   path = []
   current_node = target

   # Backtrack from the target node using predecessors
   while current_node:
       path.append(current_node)
       current_node = predecessors[current_node]

   # Reverse the path and return it
   path.reverse()

   return path
Didukung oleh

Dengan menggunakan fungsi shortest_distances, kita menghasilkan dictionary predecessors. Lalu, kita memulai loop while yang melangkah mundur satu node dari node saat ini di setiap iterasi hingga mencapai node sumber. Kemudian, kita kembalikan daftar yang sudah dibalik, yang berisi jalur dari sumber ke target.

Mari kita uji:

G = Graph(graph)

G.shortest_path("B", "F")
Didukung oleh

['B', 'E', 'C', 'F']Didukung oleh

Berhasil! Mari coba yang lain:

G.shortest_path("A", "G")Didukung oleh

['A', 'C', 'F', 'G']Didukung oleh

Persis seperti yang diharapkan.

Kesimpulan

Dalam tutorial ini, kita mempelajari salah satu algoritma paling fundamental dalam teori graf — Dijkstra. Ini sering menjadi algoritma andalan untuk menemukan jalur terpendek antara dua titik dalam struktur mirip graf. Karena kesederhanaannya, algoritma ini memiliki penerapan di banyak industri seperti:

• Logistik dan transportasi
• Jaringan dan telekomunikasi
• Manufaktur dan robotika
• Keuangan dan investasi
• Perencanaan kota

Saya harap menerapkan algoritma Dijkstra di Python memicu minat Anda pada dunia algoritma graf yang menakjubkan. Jika Anda ingin belajar lebih lanjut, saya sangat merekomendasikan sumber berikut:

• Kursus Introduction to Network Analysis in Python
• Kursus Data Structures And Algorithms in Python