5. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
A | B | C | D | E | F | |
A | 3 | 29 | ||||
B | 3 | 11 | 3 | 8 | ||
C | 11 | 4 | ||||
D | 3 | 2 | ||||
E | 29 | 8 | 4 | 2 | 7 | |
F | 7 |
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Ответ 15
Решение:
Изобразим с помощью графа данные таблицы. Точками обозначим населенные пункты. Там, где пункты соединены дорогой, там соединяем точки.
A - B - C - E - F = 3 + 11 + 3 + 7 = 24
A - B - E - F = 3 + 8 + 7 =18
A - E - F = 29 + 7 = 36
A - B - D - E - F = 3 + 3 + 2 + 7 = 15