BÀI TẬP
2.15. Tìm đường đi ngắn nhất từ A đến D trong đồ thị có trọng số trên Hình 2.33.
Bài Làm:
Ta có bảng sau:
|
A |
B |
C |
E |
F |
D |
|
(0, A)
|
( $\infty$,-) |
($\infty$,-) |
($\infty$,-)
|
($\infty$,-)
|
($\infty$,-)
|
|
- |
(4, A) |
- |
- |
(3, A)* |
(20, A) |
|
- |
(4, A)* |
(8, F) |
(18, F) |
- |
- |
|
- |
- |
(8, F)* |
(13, B) |
- |
- |
|
- |
- |
- |
(10, C)* |
- |
(18, C) |
|
- |
- |
- |
- |
- |
(17, E) |
|
(0, A) |
(4, A) |
(8, F) |
(10, C) |
(3, A) |
(17, E) |
Đường đi ngắn nhất từ A đến D là AFCED với độ dài 17.
