Triển khai thuật toán Dijkstra trong Python: Hướng dẫn từng bước

Vì sao nên học thuật toán Dijkstra?

Dijkstra là thuật toán tiêu chuẩn để tìm đường đi ngắn nhất giữa hai điểm trong một mạng, với rất nhiều ứng dụng. Đây là kiến thức nền tảng trong khoa học máy tính và lý thuyết đồ thị. Hiểu và biết cách triển khai thuật toán này sẽ mở ra cánh cửa tới nhiều thuật toán và ứng dụng đồ thị nâng cao hơn.

Thuật toán cũng dạy một cách tiếp cận giải quyết vấn đề hữu ích thông qua chiến lược tham lam (greedy), tức là đưa ra lựa chọn tối ưu ở mỗi bước dựa trên thông tin hiện có.

Kỹ năng này có thể chuyển giao sang các thuật toán tối ưu hóa khác. Thuật toán Dijkstra có thể không hiệu quả nhất trong mọi kịch bản, nhưng thường là đường cơ sở tốt khi giải các bài toán “khoảng cách ngắn nhất”.

Ví dụ bao gồm:

• Hệ thống định vị GPS tìm tuyến đường nhanh nhất
• Định tuyến gói dữ liệu trong mạng máy tính
• Dịch vụ giao hàng tối ưu hóa lộ trình để tăng hiệu quả
• Mạng xã hội (gợi ý kết nối)
• Tài chính (tìm lộ trình đầu tư tối ưu)
• Quản lý dự án (tìm quy trình làm việc hiệu quả nhất)

Ngay cả khi bạn không quan tâm đến các ví dụ trên, việc triển khai thuật toán Dijkstra trong Python vẫn giúp bạn luyện tập các khái niệm quan trọng như:

• Lớp (class) trong Python
• Dictionary comprehension
• List comprehension
• Hàng đợi ưu tiên (priority queue)

Các khái niệm then chốt liên quan đến đồ thị

Để triển khai thuật toán Dijkstra trong Python, chúng ta cần ôn lại một vài khái niệm cốt lõi từ lý thuyết đồ thị. Trước hết là chính đồ thị (graph):

Đồ thị là tập hợp các nút (đỉnh) được nối với nhau bằng các cạnh. Nút biểu diễn thực thể hay điểm trong một mạng, còn cạnh biểu diễn kết nối hay mối quan hệ giữa chúng.

Đồ thị có thể có trọng số hoặc không. Trong đồ thị không trọng số, mọi cạnh có cùng trọng số (thường là 1). Trong đồ thị có trọng số, mỗi cạnh có một trọng số đi kèm, thường biểu diễn chi phí, khoảng cách hoặc thời gian.

Trong hướng dẫn này, chúng ta sẽ dùng đồ thị có trọng số vì thuật toán Dijkstra yêu cầu như vậy.

Một đường đi trong đồ thị là chuỗi các nút được nối bằng cạnh, bắt đầu và kết thúc tại các nút cụ thể. Đường đi ngắn nhất, đối tượng chúng ta quan tâm trong hướng dẫn này, là đường có tổng trọng số nhỏ nhất (khoảng cách, chi phí, v.v.).

Giải thích trực quan thuật toán Dijkstra

Trong phần còn lại của hướng dẫn, chúng ta sẽ dùng đồ thị cuối cùng vừa xem:

Hãy thử tìm đường đi ngắn nhất giữa điểm B và F bằng thuật toán Dijkstra trong số ít nhất bảy đường đi khả dĩ. Ban đầu, chúng ta sẽ thực hiện trực quan rồi sau đó mới triển khai bằng mã.

Trước tiên, khởi tạo thuật toán như sau:

1. Đặt B làm nút gốc (nguồn).
2. Đặt khoảng cách giữa B và tất cả nút khác là vô cực làm giá trị tạm thời ban đầu. Giá trị của B là 0 vì đó là khoảng cách đến chính nó:

Sau đó, lặp lại các bước sau:

1. Chọn nút có giá trị nhỏ nhất làm “nút hiện tại” và thăm tất cả nút láng giềng của nó. Khi thăm từng láng giềng, cập nhật giá trị tạm thời của chúng từ vô cực thành tổng trọng số cạnh từ nút nguồn.
2. Sau khi thăm tất cả láng giềng của nút hiện tại, đánh dấu nút hiện tại là “đã thăm”. Khi một nút được đánh dấu “đã thăm”, giá trị của nó đã là đường đi ngắn nhất từ nguồn đến nút đó.
3. Thuật toán quay lại bước 1 và chọn nút có giá trị nhỏ nhất.

Trong đồ thị của chúng ta, B có ba láng giềng — A, D và E. Hãy thăm từng nút bắt đầu từ nút gốc và cập nhật giá trị của chúng (vòng lặp 1) dựa trên trọng số cạnh:

Ở vòng lặp 2, ta lại chọn nút có giá trị nhỏ nhất, lần này là — E. Láng giềng của E là C, D và G. B bị loại vì đã được thăm. Hãy cập nhật giá trị của các láng giềng của E:

Ta đặt giá trị của C là 5.6 vì giá trị của nó là tổng tích lũy các trọng số từ B đến C. G cũng vậy. Tuy nhiên, bạn sẽ thấy giá trị của D vẫn là 3.5 trong khi lẽ ra phải là 3.5 + 2.8 = 6.3, giống như các nút khác.

Quy tắc là nếu tổng tích lũy mới lớn hơn giá trị hiện tại của nút, chúng ta sẽ không cập nhật vì nút đó đã có khoảng cách ngắn nhất đến nút gốc. Trong trường hợp này, giá trị hiện tại 3.5 của D đã là khoảng cách ngắn nhất đến B vì chúng là láng giềng trực tiếp.

Tiếp tục như vậy cho đến khi tất cả nút đều được thăm. Khi đó, ta có khoảng cách ngắn nhất từ B đến từng nút và chỉ cần tra giá trị từ B đến F.

Tóm lại, các bước là:

1. Khởi tạo đồ thị với nút nguồn có giá trị 0 và các nút còn lại là vô cực. Bắt đầu với nguồn làm “nút hiện tại”.
2. Thăm tất cả láng giềng của nút hiện tại và cập nhật giá trị của chúng thành tổng trọng số tích lũy (khoảng cách) từ nguồn. Nếu giá trị hiện tại của láng giềng nhỏ hơn tổng tích lũy, giữ nguyên. Đánh dấu “nút hiện tại” là đã xong.
3. Đánh dấu nút chưa xong có giá trị nhỏ nhất làm “nút hiện tại”.
4. Lặp lại bước 2 và 3 cho đến khi tất cả nút đều xong.

Triển khai thuật toán Dijkstra trong Python từng bước

Bây giờ, để củng cố hiểu biết của bạn về thuật toán Dijkstra, chúng ta sẽ học cách triển khai trong Python từng bước.

Hiểu đồ thị như các dictionary

Trước hết, ta cần một cách biểu diễn đồ thị trong Python — tùy chọn phổ biến nhất là dùng dictionary. Nếu đây là đồ thị của chúng ta:

Ta có thể biểu diễn bằng dictionary sau:

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},
}
Được hỗ trợ bởi

Mỗi khóa của dictionary là một nút và mỗi giá trị là một dictionary chứa các láng giềng của khóa đó cùng khoảng cách đến chúng. Đồ thị của chúng ta có bảy nút, tức dictionary phải có bảy khóa.

Nhiều tài liệu gọi dictionary trên là danh sách kề dạng dictionary (dictionary adjacency list). Từ đây, chúng ta cũng sẽ dùng thuật ngữ đó.

1. Tạo lớp Graph

Để mã nguồn mô-đun và dễ theo dõi hơn, ta sẽ triển khai một lớp Graph đơn giản để biểu diễn đồ thị. Bên dưới, lớp sẽ dùng danh sách kề dạng dictionary. Lớp cũng có phương thức để dễ dàng thêm kết nối giữa hai nút:

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
Được hỗ trợ bởi

Dùng lớp này, ta có thể dựng đồ thị từng bước từ đầu như sau:

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)

...
Được hỗ trợ bởi

Hoặc ta có thể truyền trực tiếp danh sách kề dạng dictionary, cách này nhanh hơn:

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

G.graph
Được hỗ trợ bởi

{'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}}
Được hỗ trợ bởi

2. Dùng dictionary để lưu khoảng cách từ nguồn

Chúng ta tạo thêm một phương thức lớp — lần này cho chính thuật toán — 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

       ...
Được hỗ trợ bởi

Việc đầu tiên bên trong phương thức là định nghĩa một dictionary chứa các cặp nút - giá trị. Dictionary này được cập nhật mỗi khi ta thăm một nút và các láng giềng của nó. Như đã nói trong phần giải thích trực quan, giá trị ban đầu của mọi nút là vô cực, còn nút nguồn có giá trị 0.

Khi hoàn thiện phương thức, dictionary này sẽ được trả về và chứa khoảng cách ngắn nhất từ nguồn đến mọi nút. Ta có thể tìm khoảng cách từ B đến F như sau:

# 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}")
Được hỗ trợ bởi

3. Dùng hàng đợi ưu tiên để lặp qua các nút

Giờ chúng ta cần cách lặp qua các nút của đồ thị theo đúng quy tắc của thuật toán Dijkstra. Nhớ rằng ở mỗi vòng lặp, ta cần chọn nút có giá trị nhỏ nhất và thăm các láng giềng của nó.

Bạn có thể nghĩ rằng chỉ cần lặp qua các khóa của dictionary:

for node in graph.keys():
   ...
Được hỗ trợ bởi

Cách này không hiệu quả vì không có cách nào sắp xếp các nút theo giá trị của chúng. Do đó, mảng thông thường là chưa đủ. Để giải quyết phần này, chúng ta sẽ dùng hàng đợi ưu tiên (priority queue).

Một hàng đợi ưu tiên giống như danh sách thông thường, nhưng mỗi phần tử có thêm một giá trị biểu diễn độ ưu tiên. Đây là ví dụ về một hàng đợi ưu tiên:

pq = [(3, "A"), (1, "C"), (7, "D")]Được hỗ trợ bởi

Hàng đợi này có ba phần tử — A, C và D — và mỗi phần tử có giá trị ưu tiên quyết định cách thao tác trên hàng đợi. Python cung cấp thư viện tích hợp heapq để làm việc với hàng đợi ưu tiên:

from heapq import heapify, heappop, heappushĐược hỗ trợ bởi

Thư viện có ba hàm chúng ta cần quan tâm:

• heapify: Biến một danh sách các bộ (priority, value) thành hàng đợi ưu tiên.
• heappush: Thêm một phần tử vào hàng đợi kèm giá trị ưu tiên.
• heappop: Loại bỏ và trả về phần tử có độ ưu tiên cao nhất (phần tử có giá trị nhỏ nhất).

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

# Convert into a queue object
heapify(pq)

# Return the highest priority value
heappop(pq)
Được hỗ trợ bởi

(1, 'C')Được hỗ trợ bởi

Như bạn thấy, sau khi chuyển pq thành hàng đợi bằng heapify, ta có thể lấy ra C dựa trên độ ưu tiên. Hãy thử thêm một giá trị:

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

heappop(pq)
Được hỗ trợ bởi

(0, 'B')Được hỗ trợ bởi

Hàng đợi được cập nhật đúng theo độ ưu tiên của phần tử mới vì heappop trả về phần tử mới có ưu tiên 0.

Lưu ý rằng sau khi pop một phần tử, nó không còn trong hàng đợi nữa.

Bây giờ quay lại thuật toán, sau khi khởi tạo distances, ta tạo một hàng đợi ưu tiên mới chỉ chứa nút nguồn ban đầu:

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()
Được hỗ trợ bởi

Độ ưu tiên của mỗi phần tử trong pq sẽ là giá trị hiện tại của nó. Ta cũng khởi tạo một tập rỗng để ghi nhận các nút đã thăm.

4. Thuật toán Dijkstra dưới dạng vòng lặp while

Bây giờ, ta bắt đầu lặp qua tất cả nút chưa thăm bằng vòng lặp 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
Được hỗ trợ bởi

Khi hàng đợi ưu tiên chưa rỗng, ta tiếp tục pop phần tử có độ ưu tiên cao nhất (giá trị nhỏ nhất) và trích xuất giá trị cùng tên nút vào current_distance và current_node. Nếu current_node đã nằm trong visited, ta bỏ qua. Nếu chưa, đánh dấu là đã thăm rồi chuyển sang thăm các láng giềng của nó:

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
Được hỗ trợ bởi

Với mỗi láng giềng, ta tính khoảng cách tạm thời từ nút hiện tại bằng cách cộng trọng số cạnh nối. Sau đó kiểm tra xem khoảng cách này có nhỏ hơn khoảng cách của láng giềng trong distances hay không. Nếu có, cập nhật dictionary distances và thêm láng giềng cùng khoảng cách tạm thời vào hàng đợi ưu tiên.

Xong! Chúng ta đã triển khai thuật toán Dijkstra. Hãy kiểm thử:

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}")
Được hỗ trợ bởi

{'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
Được hỗ trợ bởi

Vậy khoảng cách từ B đến F là 9.1. Nhưng khoan: đó là đường nào?

5. Xây dựng đường đi ngắn nhất

Hiện tại, chúng ta chỉ có các khoảng cách ngắn nhất chứ chưa có đường đi, khiến đồ thị trông như sau:

Để dựng đường đi ngắn nhất từ khoảng cách đã tính, ta có thể lần ngược từ nút đích. Với mỗi cạnh nối đến F, ta trừ đi trọng số của nó:

1. 9.1–3.5 = 5.6
2. 9.1–2.5 = 6.5

Sau đó, xem liệu kết quả nào khớp với giá trị của láng giềng của F. Chỉ 5.6 khớp với giá trị của C, nghĩa là C nằm trên đường đi ngắn nhất.

Lặp lại quá trình này với láng giềng của C là A và E:

1. 5.6–3 = 2.6
2. 5.6–2.8 = 2.8

Vì 2.8 khớp với giá trị của E, E thuộc đường đi ngắn nhất. E cũng là láng giềng của B, vậy đường đi ngắn nhất giữa B và F là — BECF.

Hãy thêm phần triển khai quá trình này vào lớp của chúng ta. Mã có chút khác so với giải thích ở trên vì nó tìm đường đi ngắn nhất giữa B và tất cả nút khác, không chỉ F.

Ngoài ra, nó làm theo hướng ngược lại, nhưng ý tưởng thì giống nhau.

Thêm các dòng mã sau vào cuối phương thức shortest_distances và xóa câu lệnh return cũ:

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
Được hỗ trợ bởi

Khi mã chạy, dictionary predecessors sẽ chứa nút cha trực tiếp của mỗi nút nằm trên đường đi ngắn nhất đến nguồn. Thử nhé:

G = Graph(graph)

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

print(predecessors)
Được hỗ trợ bởi

{'A': 'B', 'B': None, 'C': 'E', 'D': 'B', 'E': 'B', 'F': 'C', 'G': 'E'}Được hỗ trợ bởi

Đầu tiên, hãy tìm đường đi ngắn nhất thủ công bằng dictionary predecessors bằng cách lần ngược từ F:

# Check the predecessor of F
predecessors["F"]
Được hỗ trợ bởi

'C'  # It is CĐược hỗ trợ bởi

# Check the predecessor of C
predecessors["C"]
Được hỗ trợ bởi

'E'  # It is EĐược hỗ trợ bởi

# Check the predecessor of E
predecessors["E"]
Được hỗ trợ bởi

'B'  # It is BĐược hỗ trợ bởi

Vậy là xong! Dictionary cho biết chính xác đường đi ngắn nhất giữa B và F là BECF.

Nhưng chúng ta vừa làm bán thủ công. Ta muốn một phương thức tự động trả về đường đi ngắn nhất dựng từ dictionary predecessors cho bất kỳ nguồn và đích nào. Ta định nghĩa phương thức này là shortest_path (thêm vào cuối lớp):

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
Được hỗ trợ bởi

Bằng cách dùng hàm shortest_distances, ta tạo dictionary predecessors. Sau đó, bắt đầu vòng lặp while lần ngược từ nút hiện tại về một nút mỗi bước cho đến khi tới nút nguồn. Cuối cùng, trả về danh sách đã đảo ngược, chứa đường đi từ nguồn đến đích.

Hãy kiểm thử:

G = Graph(graph)

G.shortest_path("B", "F")
Được hỗ trợ bởi

['B', 'E', 'C', 'F']Được hỗ trợ bởi

Hoạt động tốt! Thử thêm một trường hợp nữa:

G.shortest_path("A", "G")Được hỗ trợ bởi

['A', 'C', 'F', 'G']Được hỗ trợ bởi

Chuẩn không cần chỉnh.

Kết luận

Trong hướng dẫn này, chúng ta đã học một trong những thuật toán cơ bản nhất trong lý thuyết đồ thị — Dijkstra. Đây thường là thuật toán được chọn để tìm đường đi ngắn nhất giữa hai điểm trong các cấu trúc dạng đồ thị. Nhờ sự đơn giản, nó có ứng dụng trong nhiều lĩnh vực như:

• Logistics và vận tải
• Mạng và viễn thông
• Sản xuất và robot
• Tài chính và đầu tư
• Quy hoạch đô thị

Hy vọng việc triển khai thuật toán Dijkstra trong Python đã khơi gợi hứng thú của bạn với thế giới tuyệt vời của các thuật toán đồ thị. Nếu muốn học thêm, tôi rất khuyến nghị các tài nguyên dưới đây:

• Khóa học Nhập môn Phân tích Mạng trong Python
• Khóa học Cấu trúc Dữ liệu và Thuật toán trong Python