Given a weighted graph below and you are using the Dijkstra algorithm to find the shortest path from the vertex A to the vertex B. What is the label of the vertex D when the shortest path from A to B is determined?

Đáp án đúng: "5". Các cung là A sang C nặng 3, A sang D nặng 21, A sang E nặng 6, A sang B nặng 11, C sang D nặng 2, D sang B nặng 5, E sang D nặng 11, E sang B nặng 2. Chạy Dijkstra từ A: cố định A với nhãn 0 rồi cập nhật C bằng 3, E bằng 6, B bằng 11, D bằng 21. Đỉnh tạm nhỏ nhất là C với 3, qua cung C sang D nhãn của D hạ xuống 3 + 2 = 5. Tiếp đó cố định D với 5 và hạ nhãn của B xuống 5 + 5 = 10. Rồi cố định E với 6 và hạ nhãn của B xuống 6 + 2 = 8. Khi B được cố định với 8, tức đường ngắn nhất từ A tới B đã xác định, nhãn của D đang là 5. Con số "21" là nhãn tạm ban đầu lấy từ cung trực tiếp A sang D, bị thay ngay khi C được cố định. Con số "17" ứng với đường qua E là 6 + 11, lớn hơn 5 nên chưa bao giờ được nhận. Phương án "infinity" chỉ đúng nếu D không tới được từ A, nhưng D đã có nhãn hữu hạn ngay từ lần cập nhật đầu tiên.