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