Между населенными пунктами A, B, C, D, E, F построены дороги. Протяженность дорог приведена в таблице. Если в таблице числа отсутствуют, значит прямой дороги между пунктами нет.

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Не все понимают, как работать с таблицей. Давайте разберемся.

Возьмем первую строку:

Это дороги из пункта А. Строка показывает, что из него ведут пути в пункт С и в пункт E, и длина путей 4 и 9 соответственно.

Для решения отобразим все пути на графе и на рёбрах графа отобразим расстояние между пунктами:

1. Из пункта А пути ведут в C и в E:

2. Из пункта B пути ведут в C и в E:

3. Из пункта С пути ведут в A, B, E. Пути в пункты A и B у нас уже обозначены, осталось отобразить путь в Е:

4. Из пункта D пути ведут в E и в F:

Пути из пункта E и пункта F уже отображены. Осталось посчитать длину кратчайшего пути:

То есть длина кратчайшего пути равна 4+3+16+7=30

Ответ: 30