Не решены задание
На рисунке схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Стрелки на схеме: А→Б, А→В, А→Г, Б→В, Б→Д, Г→В, Г→Е, В→Д, В→Е, В→К, Д→К, Е→К.
Пусть
Число путей в город равно сумме чисел путей во все города, из которых в него ведут стрелки.
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице:
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 2 | 5 | 9 | |||
| B | 2 | 2 | 1 | 5 | ||
| C | 5 | 2 | 1 | |||
| D | 1 | |||||
| E | 1 | 1 | ||||
| F | 9 | 5 | 1 |
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Дороги: A–B =
Переберём пути из A в F:
- A–F:
- A–B–F:
- A–C–E–F:
- A–B–C–E–F:
Путь через D ведёт в тупик, так как у D есть только дорога в B. Наименьшая длина равна
Выписываем дороги из таблицы, перебираем пути из A в F и выбираем самый короткий.
