Tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại trong đồ thị sau. Đỉnh E được gán trọng số nhỏ nhất là?
Trả lời:
Đáp án đúng: D
Để tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại trong đồ thị, ta có thể sử dụng thuật toán Dijkstra.
1. **Khởi tạo:**
- Gán khoảng cách từ A đến A là 0.
- Gán khoảng cách từ A đến tất cả các đỉnh còn lại là vô cùng.
2. **Duyệt các đỉnh:**
- Bắt đầu từ đỉnh A.
- Tìm đỉnh kề với A mà khoảng cách từ A đến đỉnh đó là nhỏ nhất.
- Cập nhật khoảng cách từ A đến các đỉnh kề của đỉnh vừa tìm được nếu đi qua đỉnh đó mà khoảng cách ngắn hơn.
- Lặp lại quá trình này cho đến khi tất cả các đỉnh đã được duyệt.
Áp dụng thuật toán Dijkstra vào đồ thị đã cho, ta có:
- Khoảng cách từ A đến B là 2.
- Khoảng cách từ A đến C là 5 (A -> B -> C).
- Khoảng cách từ A đến D là 7 (A -> B -> C -> D).
- Khoảng cách từ A đến E là 4 (A -> B -> E).
Vậy đỉnh E được gán trọng số nhỏ nhất là 4.
