Trong khi tìm đỉnh có chi phí nhỏ nhất để cập nhật chi phí các đỉnh, có thể dùng cấu trúc hàng đợi có thứ tự từ nhỏ đến lớn (phần tử đầu hàng đợi có chi phí nhỏ nhất) để giảm bớt độ phức tạp của thuật toán Dijkstra: