28. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице: A—B — 8, A—C — 3, B—D — 3, C—E — 4, C—F — 3, D—E — 1, D—F — 3, E—F — 2. Определите длину кратчайшего пути между пунктами A и D (передвигаться можно только по построенным дорогам).

Question

Вопрос:

Accepted Answer

Рассмотрим пути из A в D. Через C и E получаем путь A—C—E—D длиной \(3+4+1=8\) км.

Другие возможные пути короче не будут: A—B—D имеет длину \(8+3=11\) км, а A—C—F—D — \(3+3+3=9\) км.

Ответ: 8 км.