2.16. Tìm đường đi ngắn nhất từ đỉnh S đến mỗi đỉnh khác của đồ thị có trọng số trên Hình 2.34.
Bài Làm:
|
S |
A |
B |
C |
D |
E |
F |
|
(0,S) |
($\infty$ ,-) |
($\infty$,-)
|
($\infty$,-)
|
($\infty$,-)
|
($\infty$,-)
|
($\infty$,-)
|
|
- |
(2, S) |
(1, S)* |
(7, S) |
- |
- |
- |
|
- |
(2, S)* |
- |
(6, B) |
(13, B) |
(16, B) |
(10, B) |
|
- |
- |
- |
- |
(7, A)* |
(10, A) |
- |
|
- |
- |
- |
- |
- |
(9, D)* |
- |
|
- |
- |
- |
- |
- |
- |
(15, E) |
|
(0, S) |
(2, S) |
(1, S) |
|
(7, A) |
(9, D) |
(15, E) |
Đường đi ngắn nhất từ đỉnh S đến đỉnh F: SADEF, có độ dài 15.
Đường đi ngắn nhất từ đỉnh S đến đỉnh A: SA, có độ dài 2.
Đường đi ngắn nhất từ đỉnh S đến đỉnh B: SB, có độ dài 1.
Đường đi ngắn nhất từ đỉnh S đến đỉnh C: SBC, có độ dài 6.
Đường đi ngắn nhất từ đỉnh S đến đỉnh D: SAD, có độ dài 7.
Đường đi ngắn nhất từ đỉnh S đến đỉnh E: SADE, có độ dài 9.
