Với đồ thị n đỉnh, độ phức tạp tính toán của thuật toán Dijkstra là:

Thuật toán Dijsktra

Tìm kiếm theo chiều rộng (BFS)

Tìm kiếm theo chiều sâu (DFS)

Thuật toán Prim

giữa hai đỉnh bất kỳ i, j ∈V, có nhiều nhất một cạnh, có kể đến thứ tự các đỉnh

Giữa hai đỉnh bất kỳ i, j ∈ V, có nhiều nhất một cạnh

Giữa hai đỉnh bất kỳ i, j ∈ V, có thể có nhiều hơn một cạnh, có kể đến thứ tự các đỉnh

Giữa hai đỉnh bất kỳ i, j ∈ V, có thể có nhiều hơn một cạnh, không kể đến thứ tự các đỉnh

u, v×V và u, v có thứ tự

u, v×V và u, v có thứ tự

u, v×V và u, v không có thứ tự

u, v×V và u, v không có thứ tự

Các cạnh e1, e2, …, en kề nhau

Các đỉnh v0 = s, v1, v2, …, vn = t kề nhau, các cạnh ei=(vi-1,vi) đôi một khác nhau, i = 0…n

Các cạnh e1, e2, …, en không kề nhau

Các đỉnh v0 = s, v1, v2, …, vn = t không kề nhau

Phụ thuộc vào số đỉnh của đồ thị

Là một số lẻ

Là một số chẵn

Phụ thuộc vào số cạnh của đồ thị

Số cạnh đi vào đỉnh đó

Số cạnh đi ra khỏi đỉnh đó

Tổng của cạnh đi vào và số cạnh đi ra khỏi đỉnh đó

Hiệu của cạnh đi vào và cạnh đi ra khỏi đỉnh đó

n, n+1

n, n

n, n-1

n, 2n

Tất cả các đỉnh của G

Tất cả các đỉnh của G trừ đỉnh phát s

Tất cả các đỉnh của G rừ đỉnh thu t

Tất cả các đỉnh của G trừ đỉnh phát s và đỉnh thu t

3, 3, 4, 6, 4

3, 4, 6, 4, 4

3, 4, 6, 4, 5

3, 4, 5, 4, 4

K, I, A, C, E, G, B, D, F, H

K, I, A, B, C, D, E, F, G, H

K, I, A, B, C, D, F, H, G, E

K, A, C, D, B, I, G, H, F, E