Độ phức tạp thời gian và không gian

Độ phức tạp thời gian:

• O(V² + V*E) như được viết ở đây (mỗi vòng trong V vòng quét các đỉnh để tìm đỉnh có giá trị nhỏ nhất và quét các cạnh để nới lỏng). Dùng heap nhị phân và danh sách kề sẽ cải thiện độ phức tạp thành O((V + E) log V).

Độ phức tạp không gian:

• O(V) cho các mảng khoảng cách và đã thăm (cộng thêm các cạnh đầu vào).

Tóm tắt:

• Dijkstra tìm khoảng cách ngắn nhất từ một nguồn cho các trọng số không âm bằng cách tham lam chốt đỉnh gần nhất và nới lỏng các cạnh của đỉnh đó.
• Thuật toán này không hoạt động với cạnh âm; hãy dùng Bellman-Ford cho các cạnh đó.