Thuật toán DSA Dijkstra
Thuật toán đường đi ngắn nhất của Dijkstra được phát minh vào năm 1956 bởi nhà khoa học máy tính người Hà Lan Edsger W. Dijkstra trong một giờ giải lao uống cà phê kéo dài 20 phút, khi đang đi mua sắm với vợ sắp cưới ở Amsterdam.
Lý do phát minh ra thuật toán này là để thử nghiệm một máy tính mới có tên ARMAC.
Thuật toán Dijkstra
Thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác.
Nó làm như vậy bằng cách liên tục chọn đỉnh chưa được thăm gần nhất và tính toán khoảng cách tới tất cả các đỉnh lân cận chưa được thăm.
Thuật toán Dijkstra thường được coi là thuật toán đơn giản nhất để giải bài toán đường đi ngắn nhất.
Thuật toán Dijkstra được sử dụng để giải các bài toán đường đi ngắn nhất một nguồn cho đường đi có hướng hoặc không có hướng. Nguồn đơn có nghĩa là một đỉnh được chọn làm điểm bắt đầu và thuật toán sẽ tìm đường đi ngắn nhất từ đỉnh đó đến tất cả các đỉnh khác.
Thuật toán Dijkstra không áp dụng được cho đồ thị có cạnh âm. Đối với các đồ thị có cạnh âm, có thể sử dụng thuật toán Bellman-Ford được mô tả ở trang tiếp theo.
Để tìm đường đi ngắn nhất, thuật toán của Dijkstra cần biết đỉnh nào là nguồn, nó cần một cách để đánh dấu các đỉnh là đã ghé thăm và nó cần một cái nhìn tổng quan về khoảng cách ngắn nhất hiện tại tới mỗi đỉnh khi nó di chuyển qua biểu đồ, cập nhật những khoảng cách này khi tìm thấy một khoảng cách ngắn hơn.
Làm thế nào nó hoạt động:
- Đặt khoảng cách ban đầu cho tất cả các đỉnh: 0 cho đỉnh nguồn và vô cực cho tất cả các đỉnh còn lại.
- Chọn đỉnh chưa được thăm có khoảng cách ngắn nhất tính từ điểm bắt đầu làm đỉnh hiện tại. Vì vậy, thuật toán sẽ luôn bắt đầu với nguồn là đỉnh hiện tại.
- Đối với mỗi đỉnh lân cận chưa được thăm của đỉnh hiện tại, hãy tính khoảng cách từ nguồn và cập nhật khoảng cách nếu khoảng cách mới được tính toán thấp hơn.
- Bây giờ chúng ta đã hoàn thành đỉnh hiện tại, vì vậy chúng ta đánh dấu nó là đã ghé thăm. Một đỉnh đã ghé thăm sẽ không được kiểm tra lại.
- Quay lại bước 2 để chọn một đỉnh hiện tại mới và tiếp tục lặp lại các bước này cho đến khi đi qua tất cả các đỉnh.
- Cuối cùng, chúng ta còn lại đường đi ngắn nhất từ đỉnh nguồn đến mọi đỉnh khác trong biểu đồ.
Trong hoạt ảnh ở trên, khi một đỉnh được đánh dấu là đã ghé thăm, đỉnh đó và các cạnh của nó sẽ mờ đi để biểu thị rằng thuật toán của Dijkstra hiện đã được thực hiện với đỉnh đó và sẽ không truy cập lại đỉnh đó nữa.
Lưu ý: Phiên bản cơ bản này của thuật toán Dijkstra cung cấp cho chúng ta giá trị của chi phí đường đi ngắn nhất tới mọi đỉnh, chứ không phải đường đi thực tế là gì. Vì vậy, ví dụ, trong hình ảnh động ở trên, chúng ta nhận được giá trị đường đi ngắn nhất là 10 đến đỉnh F, nhưng thuật toán không cung cấp cho chúng ta đỉnh nào (D->E->C->D->F) tạo nên đường đi ngắn nhất này con đường. Chúng tôi sẽ bổ sung thêm chức năng này ở dưới đây trên trang này.
Mô phỏng Dijkstra chi tiết
Chạy mô phỏng bên dưới để hiểu chi tiết hơn về cách thuật toán Dijkstra chạy trên một biểu đồ cụ thể, tìm khoảng cách ngắn nhất từ đỉnh D.
Mô phỏng này cho thấy cách tính khoảng cách từ đỉnh D đến tất cả các đỉnh khác, bằng cách luôn chọn đỉnh tiếp theo là đỉnh chưa được thăm gần nhất tính từ điểm bắt đầu.
Hãy làm theo mô tả từng bước bên dưới để biết tất cả thông tin chi tiết về cách thuật toán Dijkstra tính toán khoảng cách ngắn nhất.
Chạy qua thủ công
Hãy xem xét biểu đồ dưới đây.
Chúng ta muốn tìm đường đi ngắn nhất từ đỉnh nguồn D đến tất cả các đỉnh khác, ví dụ như đường đi ngắn nhất tới C là D->E->C, với trọng số đường đi là 2+4=6.
Để tìm đường đi ngắn nhất, thuật toán Dijkstra sử dụng một mảng có khoảng cách đến tất cả các đỉnh khác và ban đầu đặt các khoảng cách này thành vô hạn hoặc một số rất lớn. Và khoảng cách đến đỉnh mà chúng ta bắt đầu từ (nguồn) được đặt thành 0.
distances = [inf, inf, inf, 0, inf, inf, inf]
#vertices [ A , B , C , D, E , F , G ]
Hình ảnh bên dưới hiển thị khoảng cách vô hạn ban đầu đến các đỉnh khác tính từ đỉnh bắt đầu D. Giá trị khoảng cách cho đỉnh D là 0 vì đó là điểm bắt đầu.
Thuật toán Dijkstra sau đó đặt đỉnh D làm đỉnh hiện tại và xem xét khoảng cách đến các đỉnh liền kề. Vì khoảng cách ban đầu tới các đỉnh A và E là vô hạn nên khoảng cách mới tới các đỉnh này được cập nhật theo trọng số của các cạnh. Vì vậy, đỉnh A được thay đổi khoảng cách từ inf thành 4 và đỉnh E được thay đổi khoảng cách thành 2. Như đã đề cập ở trang trước, việc cập nhật các giá trị khoảng cách theo cách này được gọi là 'thư giãn'.
Sau khi nới lỏng đỉnh A và E, đỉnh D được coi là đã thăm và sẽ không được thăm nữa.
Đỉnh tiếp theo được chọn làm đỉnh hiện tại phải là đỉnh có khoảng cách ngắn nhất tới đỉnh nguồn (đỉnh D), trong số các đỉnh chưa được thăm trước đó. Do đó, đỉnh E được chọn làm đỉnh hiện tại sau đỉnh D.
Khoảng cách đến tất cả các đỉnh liền kề và chưa được thăm trước đó từ đỉnh E bây giờ phải được tính toán và cập nhật nếu cần.
Khoảng cách tính được từ D đến đỉnh A, qua E, là 2+4=6. Nhưng khoảng cách hiện tại đến đỉnh A đã là 4, thấp hơn nên khoảng cách đến đỉnh A không được cập nhật.
Khoảng cách đến đỉnh C được tính là 2+4=6, nhỏ hơn vô cực, do đó khoảng cách đến đỉnh C được cập nhật.
Tương tự, khoảng cách đến nút G được tính toán và cập nhật thành 2+5=7.
Đỉnh tiếp theo cần thăm là đỉnh A vì nó có khoảng cách đến D ngắn nhất trong số tất cả các đỉnh chưa được thăm.
Khoảng cách được tính đến đỉnh C, qua A, là 4+3=7, cao hơn khoảng cách đã đặt đến đỉnh C, do đó khoảng cách đến đỉnh C không được cập nhật.
Đỉnh A hiện được đánh dấu là đã ghé thăm và đỉnh hiện tại tiếp theo là đỉnh C vì đỉnh đó có khoảng cách thấp nhất đến đỉnh D giữa các đỉnh chưa được thăm còn lại.
Đỉnh F được cập nhật khoảng cách 6+5=11 và đỉnh B được cập nhật khoảng cách 6+2=8.
Khoảng cách tính toán đến đỉnh G qua đỉnh C là 6+5=11, cao hơn khoảng cách đã đặt là 7, do đó khoảng cách đến đỉnh G không được cập nhật.
Đỉnh C được đánh dấu là đã thăm và đỉnh tiếp theo được thăm là G vì nó có khoảng cách thấp nhất giữa các đỉnh chưa được thăm còn lại.
Đỉnh F đã có khoảng cách là 11. Khoảng cách này thấp hơn khoảng cách tính toán từ G, là 7+5=12, do đó khoảng cách đến đỉnh F không được cập nhật.
Đỉnh G được đánh dấu là đã thăm và đỉnh B trở thành đỉnh hiện tại vì nó có khoảng cách thấp nhất trong số các đỉnh chưa được thăm còn lại.
Khoảng cách mới đến F qua B là 8+2=10, vì nó thấp hơn khoảng cách hiện tại của F là 11.
Đỉnh B được đánh dấu là đã thăm và không có gì để kiểm tra đỉnh F cuối cùng chưa được thăm, vì vậy thuật toán Dijkstra đã kết thúc.
Mỗi đỉnh chỉ được thăm một lần và kết quả là khoảng cách thấp nhất từ đỉnh nguồn D đến mọi đỉnh khác trong đồ thị.
Triển khai thuật toán Dijkstra
Để triển khai thuật toán Dijkstra, chúng tôi tạo một lớp Graph . Graph biểu thị đồ thị với các đỉnh và cạnh của nó:
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data Dòng 3: Chúng ta tạo adj_matrix để giữ tất cả các cạnh và trọng số của cạnh. Giá trị ban đầu được đặt thành 0 .
Dòng 4: size là số đỉnh của đồ thị.
Dòng 5: vertex_data chứa tên của tất cả các đỉnh.
Dòng 7-10: Phương thức add_edge được sử dụng để thêm một cạnh từ đỉnh u đến đỉnh v , với weight số cạnh .
Dòng 12-14: Phương thức add_vertex_data được sử dụng để thêm một đỉnh vào biểu đồ. Chỉ mục nơi đỉnh đó thuộc về được đưa ra cùng với đối vertex và data là tên của đỉnh.
Lớp Graph cũng chứa phương thức chạy thuật toán Dijkstra:
def dijkstra(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None:
break
visited[u] = True
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
return distances Dòng 18-19: Khoảng cách ban đầu được đặt thành vô cùng cho tất cả các đỉnh trong mảng distances , ngoại trừ đỉnh bắt đầu, trong đó khoảng cách là 0.
Dòng 20: Tất cả các đỉnh ban đầu được đặt thành False để đánh dấu chúng là chưa được truy cập trong mảng visited .
Dòng 23-28: Đã tìm thấy đỉnh hiện tại tiếp theo. Các cạnh đi từ đỉnh này sẽ được kiểm tra để xem liệu có thể tìm thấy khoảng cách ngắn hơn hay không. Đó là đỉnh chưa được thăm với khoảng cách thấp nhất tính từ điểm bắt đầu.
Dòng 30-31: Nếu không tìm thấy đỉnh hiện tại tiếp theo, thuật toán kết thúc. Điều này có nghĩa là tất cả các đỉnh có thể truy cập được từ nguồn đều đã được truy cập.
Dòng 33: Đỉnh hiện tại được đặt là đã ghé thăm trước khi thư giãn các đỉnh liền kề. Điều này hiệu quả hơn vì chúng ta tránh kiểm tra khoảng cách đến đỉnh hiện tại.
Dòng 35-39: Khoảng cách được tính cho các đỉnh liền kề chưa được truy cập và được cập nhật nếu khoảng cách tính toán mới thấp hơn.
Sau khi xác định lớp Graph , các đỉnh và cạnh phải được xác định để khởi tạo biểu đồ cụ thể và mã hoàn chỉnh cho ví dụ về thuật toán Dijkstra này trông như thế này:
Ví dụ
Trăn:
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def dijkstra(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None:
break
visited[u] = True
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
return distances
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(3, 0, 4) # D - A, weight 5
g.add_edge(3, 4, 2) # D - E, weight 2
g.add_edge(0, 2, 3) # A - C, weight 3
g.add_edge(0, 4, 4) # A - E, weight 4
g.add_edge(4, 2, 4) # E - C, weight 4
g.add_edge(4, 6, 5) # E - G, weight 5
g.add_edge(2, 5, 5) # C - F, weight 5
g.add_edge(2, 1, 2) # C - B, weight 2
g.add_edge(1, 5, 2) # B - F, weight 2
g.add_edge(6, 5, 5) # G - F, weight 5
# Dijkstra's algorithm from D to all vertices
print("\nDijkstra's Algorithm starting from vertex D:")
distances = g.dijkstra('D')
for i, d in enumerate(distances):
print(f"Distance from D to {g.vertex_data[i]}: {d}") Chạy ví dụ »Thuật toán Dijkstra trên đồ thị có hướng
Để chạy thuật toán Dijkstra trên đồ thị có hướng, cần rất ít thay đổi.
Tương tự như thay đổi chúng ta cần để phát hiện chu trình cho đồ thị có hướng , chúng ta chỉ cần xóa một dòng mã để ma trận kề không còn đối xứng nữa.
Hãy triển khai đồ thị có hướng này và chạy thuật toán Dijkstra từ đỉnh D.
Đây là cách triển khai thuật toán Dijkstra trên đồ thị có hướng, với D là đỉnh nguồn:
Ví dụ
Trăn:
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
#self.adj_matrix[v][u] = weight For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def dijkstra(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None:
break
visited[u] = True
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
return distances
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(3, 0, 4) # D -> A, weight 5
g.add_edge(3, 4, 2) # D -> E, weight 2
g.add_edge(0, 2, 3) # A -> C, weight 3
g.add_edge(0, 4, 4) # A -> E, weight 4
g.add_edge(4, 2, 4) # E -> C, weight 4
g.add_edge(4, 6, 5) # E -> G, weight 5
g.add_edge(2, 5, 5) # C -> F, weight 5
g.add_edge(1, 2, 2) # B -> C, weight 2
g.add_edge(1, 5, 2) # B -> F, weight 2
g.add_edge(6, 5, 5) # G -> F, weight 5
# Dijkstra's algorithm from D to all vertices
print("Dijkstra's Algorithm starting from vertex D:\n")
distances = g.dijkstra('D')
for i, d in enumerate(distances):
print(f"Shortest distance from D to {g.vertex_data[i]}: {d}")
Chạy ví dụ »Hình ảnh bên dưới cho chúng ta thấy khoảng cách ngắn nhất từ đỉnh D được tính bằng thuật toán Dijkstra.
Kết quả này tương tự với ví dụ trước sử dụng thuật toán Dijkstra trên đồ thị vô hướng. Tuy nhiên, có một điểm khác biệt chính: trong trường hợp này, không thể truy cập đỉnh B từ D và điều này có nghĩa là khoảng cách ngắn nhất từ D đến F bây giờ là 11 chứ không phải 10, vì đường đi không thể đi qua đỉnh B nữa.
Trả về đường dẫn từ thuật toán Dijkstra
Với một vài điều chỉnh, thuật toán Dijkstra cũng có thể trả về các đường dẫn ngắn nhất thực tế, bên cạnh các giá trị đường dẫn ngắn nhất. Vì vậy, ví dụ, thay vì chỉ trả về giá trị đường đi ngắn nhất là 10 từ đỉnh D đến F, thuật toán cũng có thể trả về giá trị đường đi ngắn nhất đó là "D->E->C->B->F".
Để trả về đường dẫn, chúng ta tạo một mảng predecessors để giữ đỉnh trước đó trong đường đi ngắn nhất cho mỗi đỉnh. Mảng predecessors có thể được sử dụng để quay lui để tìm đường đi ngắn nhất cho mọi đỉnh.
Ví dụ
Trăn:
class Graph:
# ... (rest of the Graph class)
def dijkstra(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
predecessors = [None] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None:
break
visited[u] = True
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
predecessors[v] = u
return distances, predecessors
def get_path(self, predecessors, start_vertex, end_vertex):
path = []
current = self.vertex_data.index(end_vertex)
while current is not None:
path.insert(0, self.vertex_data[current])
current = predecessors[current]
if current == self.vertex_data.index(start_vertex):
path.insert(0, start_vertex)
break
return '->'.join(path) # Join the vertices with '->'
g = Graph(7)
# ... (rest of the graph setup)
# Dijkstra's algorithm from D to all vertices
print("Dijkstra's Algorithm starting from vertex D:\n")
distances, predecessors = g.dijkstra('D')
for i, d in enumerate(distances):
path = g.get_path(predecessors, 'D', g.vertex_data[i])
print(f"{path}, Distance: {d}")
Chạy ví dụ » Dòng 7 và 29: Mảng predecessors trước tiên được khởi tạo với các giá trị None , sau đó nó được cập nhật với mảng tiền thân chính xác cho mỗi đỉnh khi các giá trị đường dẫn ngắn nhất được cập nhật.
Dòng 33-42: Phương thức get_path sử dụng mảng predecessors và trả về một chuỗi có đường đi ngắn nhất từ đỉnh đầu đến đỉnh cuối.
Thuật toán Dijkstra với một đỉnh đích duy nhất
Giả sử chúng ta chỉ quan tâm đến việc tìm đường đi ngắn nhất giữa hai đỉnh, giống như tìm khoảng cách ngắn nhất giữa đỉnh D và đỉnh F trong biểu đồ bên dưới.
Thuật toán Dijkstra thường được sử dụng để tìm đường đi ngắn nhất từ một đỉnh nguồn tới tất cả các đỉnh khác trong đồ thị, nhưng nó cũng có thể được sửa đổi để chỉ tìm đường đi ngắn nhất từ nguồn đến một đỉnh đích duy nhất, bằng cách dừng thuật toán khi đã đến đích (đã ghé thăm).
Điều này có nghĩa là đối với đồ thị cụ thể trong hình trên, thuật toán Dijkstra sẽ dừng sau khi truy cập F (đỉnh đích), trước khi truy cập các đỉnh H, I và J vì chúng ở xa D hơn F.
Dưới đây chúng ta có thể thấy trạng thái các khoảng cách được tính toán khi thuật toán Dijkstra đã tìm được khoảng cách ngắn nhất từ D đến F và dừng chạy.
Trong hình trên, đỉnh F vừa được cập nhật với khoảng cách 10 tính từ đỉnh B. Vì F là đỉnh chưa được thăm có khoảng cách thấp nhất tới D nên thông thường nó sẽ là đỉnh hiện tại tiếp theo, nhưng vì nó là đích nên thuật toán dừng . Nếu thuật toán không dừng lại, J sẽ là đỉnh tiếp theo có khoảng cách cập nhật 11+2=13, tính từ đỉnh I.
Đoạn mã dưới đây là thuật toán Dijkstra được triển khai để tìm đường đi ngắn nhất tới một đỉnh đích duy nhất:
Ví dụ
Trăn:
class Graph:
# ... (existing methods)
def dijkstra(self, start_vertex_data, end_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
end_vertex = self.vertex_data.index(end_vertex_data)
distances = [float('inf')] * self.size
predecessors = [None] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None or u == end_vertex:
print(f"Breaking out of loop. Current vertex: {self.vertex_data[u]}")
print(f"Distances: {distances}")
break
visited[u] = True
print(f"Visited vertex: {self.vertex_data[u]}")
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
predecessors[v] = u
return distances[end_vertex], self.get_path(predecessors, start_vertex_data, end_vertex_data)
# Example usage
g = Graph(7)
# ... (rest of the graph setup)
distance, path = g.dijkstra('D', 'F')
print(f"Path: {path}, Distance: {distance}")
Chạy ví dụ »Dòng 20-23: Nếu chúng ta chuẩn bị chọn đỉnh đích làm đỉnh hiện tại và đánh dấu nó là đã ghé thăm, điều đó có nghĩa là chúng ta đã tính khoảng cách ngắn nhất đến đỉnh đích và thuật toán Dijkstra có thể dừng trong trường hợp đích duy nhất này.
Độ phức tạp thời gian của thuật toán Dijkstra
Với \(V\) là số đỉnh trong biểu đồ của chúng ta, độ phức tạp về thời gian của thuật toán Dijkstra là
\[ O( V^2 ) \]
Lý do tại sao chúng ta có độ phức tạp về thời gian này là vì đỉnh có khoảng cách thấp nhất phải được tìm kiếm để chọn đỉnh hiện tại tiếp theo và việc đó cần có thời gian \(O(V)\). Và vì điều này phải được thực hiện cho mọi đỉnh được kết nối với nguồn, nên chúng ta cần tính đến yếu tố đó và do đó chúng ta nhận được độ phức tạp về thời gian \(O(V^2)\) cho thuật toán Dijkstra.
Thay vào đó, bằng cách sử dụng cấu trúc dữ liệu Min-heap hoặc Fibonacci-heap cho khoảng cách (chưa được giải thích trong hướng dẫn này), thời gian cần thiết để tìm kiếm đỉnh khoảng cách tối thiểu sẽ giảm từ \(O(V)\) xuống \(O ( \log{V})\), dẫn đến độ phức tạp về thời gian được cải thiện cho thuật toán Dijkstra
\[ O( V \cdot \log{V} + E ) \]
Trong đó \(V\) là số đỉnh trong đồ thị và \(E\) là số cạnh.
Sự cải thiện mà chúng tôi nhận được từ việc sử dụng cấu trúc dữ liệu Min-heap cho thuật toán Dijkstra đặc biệt tốt nếu chúng tôi có một biểu đồ lớn và thưa thớt, nghĩa là một biểu đồ có số lượng đỉnh lớn nhưng không có nhiều cạnh.
Việc triển khai thuật toán Dijkstra với cấu trúc dữ liệu Fibonacci-heap sẽ tốt hơn đối với các đồ thị dày đặc, trong đó mỗi đỉnh có một cạnh với hầu hết mọi đỉnh khác.
