Алгоритм O (E + V) для вычисления количества кратчайших путей между двумя узлами на данном графике

Question

Когда дан граф G с вершинами и ребрами | V | и | E | и вершины u и t, напишите алгоритм O (| E | + | V |) для вычисления количества кратчайших путей от u до t, т. е. если есть 5 путей длины 4 с длиной 4, являющейся кратчайшим путем от u к т, тогда алгоритм выведет 5.

Я знаю, что алгоритм должен каким-то образом включать DFS или BFS из-за своего времени выполнения, поскольку у каждого есть время выполнения O (| E | + | V |), но я немного застрял. Я пытался реализовать что-то, где он неоднократно выполнял бы DFS с алгоритмом, оканчивающимся на t, но это стало проблематичным для решения, какие узлы устанавливать как посещенные, а какие сбрасывать после каждой итерации.

Заранее спасибо!

Answer 1

Вы можете использовать поиск в ширину.Для каждой вершины следите за:

• кратчайшей длиной пути от u до этой вершины
  • Всякий раз, когда вы обрабатываете данную вершину, вы устанавливаете это свойство длявсе его соседи, которые еще не установили это свойство.
  • Это удваивается как флаг «уже был поставлен в очередь»: вы изначально устанавливаете значение часового типа, такое как ∞ или ∞, и обновляете его только один раздля любой данной вершины.Поэтому вам не нужен отдельный флаг для отслеживания посещенных вершин.
• количество кратчайших путей от u до этой вершины
  • Всякий раз, когда выобрабатывая данную вершину, вы увеличиваете это свойство соответствующим образом для всех ее соседей, у которых длина кратчайшего пути от u больше, чем у обрабатываемой вершины.
  • Обратите внимание, что выобновляйте это свойство много раз для некоторых вершин, но это нормально, потому что вы обновляете его только один раз для ребра.