Giáo trình Đồ thị và các thuật toán - Chương 3: Các bài toán về đường đi

Mệnh đề 3.2.2 Thuật toán Dijkstra đòi hỏi thời gian 0ện?). Nếu đô thị thưa và được các định bởi dãy liên tiếp các đỉnh, thì thời gian cực đại của thuật toán là 2(m log n). Chứng minh. Trong trường hợp đồ thị liên thông mạnh đầy đủ n định và cần tìm đường đi ngắn nhất từ S đến mọi định khác, thuật toán cần n(n - 1)/2 phép cộng và so sánh trong Birớt 2 và n(n - 1)/2 phép so sánh khác trong Bước 3. Ngoài ra, các Bước 2 và 3 cần xác định các định được gán nhãn tạm thời nên cần thêm n(n - 1)/2 phép số sánh. Các số này cũng là cận trên cho số các phép toán cần thiết để tìm đường đi ngắn nhất từ 5 đến t, và thật vậy, các giá trị này đạt được khi t là định cuối cùng được gán nhãn cố định. 4 Khỉ Thuật toán Dijkstra kết thúc, các đường đi ngắn nhất được xác định bằng đệ qui theo Phương trình (3.1) dưới đây. Do đó nếu t là đỉnh trước định vị trong đường đi ngắn