3. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
| A | 2 | 1 | 8 | |||
| B | 1 | 3 | ||||
| C | 2 | 1 | 5 | |||
| D | 1 | 1 | 4 | |||
| E | 1 | 6 | ||||
| F | 8 | 3 | 5 | 4 | 6 |
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 5 2) 7 3) 4 4) 8
Ответ: 1
Решение:
На основании таблицы, которая дана в задании, строим граф. Из пункта А можно попасть в пункты C, D и F, а из них —а из B в C, F и т.д. Затем подсчитаем длину пути по каждому маршруту и выберем наименьший из них.
ACF = 2 + 5 = 7
ADF = 1 + 4 = 5
ADEF = 1 + 1 +6 = 8
AF = 8
ACBF = 2 + 1 + 3 = 6
Итак, наш маршрут ADF и равен 5.
Ответ: 1