Bài tự luận Một số bài toán thuộc chuyên đề Toán học 10–11–12 · Bài 4
Cho đồ thị có trọng số như Hình 6.
a) Tìm tất cả các đường đi từ $A$ đến $T$ (đi qua mỗi đỉnh nhiều nhất một lần) và tính độ dài của mỗi đường đi đó.
b) Từ đó, tìm đường đi ngắn nhất từ $A$ đến $T$.
Xem lời giải
Lời giải
a) Các đường đi từ $A$ đến $T$ là:
- $ABDT,l_{ABDT}=4+7+3=14$
- $ABDCET,l_{ABDCET}=4+7+6+12+5=34$
- $ABDET,l_{ABDET}=4+7+4+5=20$
- $ACDT,l_{ACDT}=2+6+3=11$
- $ACDET,l_{ACDET}=2+6+4+5=17$
- $ACET,l_{ { \rm{ A } }{ \rm{ C } }{ \rm{ E } }{ \rm{ T } } } =2+12+5=19$
- $ACEDT,l_{ACEDT}=2+12+4+3=21$
b) Đường đi ngắn nhất từ $A$ đến $T$ là: $ACDT$.
