Подсчёт путей по графу
Подсчёт путей по графу — это определение количества различных маршрутов, по которым можно попасть из начальной вершины в конечную, переходя по рёбрам графа. Обычно число путей находят последовательным суммированием количества способов попасть в предыдущие вершины.
Основное правило
Пусть \(f(v)\) — количество способов попасть в вершину \(v\) из начальной вершины. Для начальной вершины задают \(f(s)=1\): один способ — находиться в ней в начале. Для любой другой вершины значение равно сумме значений всех вершин, из которых в неё ведёт переход.
Вершины обрабатывают в таком порядке, чтобы все предшественники вершины уже были рассмотрены. Это особенно удобно для графа без циклов: достаточно двигаться слева направо по схеме или в порядке, заданном топологической сортировкой. Если в графе есть циклы, число маршрутов может быть бесконечным, если разрешено проходить по циклу повторно.
Из вершины \(A\) идут рёбра в \(B\) и \(C\). Из \(B\) и \(C\) идут рёбра в \(D\). Тогда \(f(A)=1\), \(f(B)=1\), \(f(C)=1\), а \(f(D)=f(B)+f(C)=2\). В вершину \(D\) можно попасть двумя путями: \(A\to B\to D\) и \(A\to C\to D\).
Количество путей — не то же самое, что длина пути или расстояние между вершинами. Длина показывает число рёбер в одном маршруте, а подсчёт путей показывает, сколько разных маршрутов существует. Если требуется найти число способов, одинаковые вершины, посещённые в разном порядке, учитываются как разные пути.
В вершину \(X\) ведут рёбра из \(P\) и \(Q\). Из начальной вершины в \(P\) можно попасть 3 способами, а в \(Q\) — 5 способами. Сколько способов попасть в \(X\)?
Главное
- Для начальной вершины число способов равно 1.
- Число способов попасть в вершину равно сумме способов попасть во все вершины, из которых в неё есть переход.
- В графе с циклами при разрешённых повторных проходах число маршрутов может быть бесконечным.