Задание: Между населенными пунктами A, B, C, D, E, F, G построены дороги. Протяженность дорог приведена в таблице. Если в таблице числа отсутствуют, значит прямой дороги между пунктами нет.
| | A | B | C | D | E | F | G |
| A | | 3 | 6 | | | | 28 |
| B | 3 | | 2 | | | | |
| C | 6 | 2 | | 7 | | | 18 |
| D | | | 7 | | 2 | 7 | 12 |
| E | | | | 2 | | 3 | 5 |
| F | | | | 7 | 3 | | 1 |
| G | 28 | | 18 | 12 | 5 | 1 | |
Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).
Решение: Не все понимают, как работать с таблицей. Давайте разберемся.
Возьмем первую строку:
Это дороги из пункта А. Строка показывает, что из него ведут пути в пункты B, C, и G, и длина путей 3, 6, 28 соответственно.
Для решения отобразим все пути на графе и на рёбрах графа отобразим расстояние между пунктами.
1. Из пункта А пути ведут в пункты B, C, G:
2. Из пункта B пути ведут в А и C. Путь в A уже отображен, добавим путь в C. Из пункта C пути ведут в A, B, D, G, добавим недостающие пути:
3. Из пункта D пути ведут в C, E, F, G. Путь в C уже указан, отобразим остальные:
4. Оставшиеся пути — из E в F и G и из F в G:
Найдем в графе кратчайший путь:
Посчитаем длину: 3+2+7+2+3+1=18
Ответ: 18
