Неориентированный граф задан списком рёбер: A–B, A–C, B–D, C–D, C–E, D–F, E–F. Сколько существует различных кратчайших путей (по числу рёбер) из вершины A в вершину F?
Показать ответ и разборСкрыть ответ и разбор
Верный ответ
- A3
Разбор
Найдём расстояния от A обходом в ширину: A — 0; B и C — 1; D и E — 2; F — 3. Число кратчайших путей в вершину равно сумме этих чисел по соседям на предыдущем уровне: в B один путь, в C один путь, в D два пути (через B и через C), в E один путь (через C). В F приходят D и E, поэтому 2 + 1 = 3 пути: A–B–D–F, A–C–D–F, A–C–E–F. Значение «4» получится, если посчитать все простые пути, включая более длинный A–B–D–C–E–F. Значение «2» получится, если учесть только пути через D.