Как найти число различных кратчайших путей между двумя вершинами, в ориентированном графе и с линейным временем?

Ответ 1

Вот некоторые идеи по этому поводу.

• Может быть только несколько кратчайших путей от v- > w до node x либо при наличии нескольких путей в x через одну и ту же вершину, либо если x встречается многократно на одном уровне DFS.

Доказательство. Если в x есть несколько путей через одну и ту же вершину, существует много разных путей через x. Это просто. Предположим теперь, что есть только один путь в x через каждую вершину, идущую в x (максимум).

Если раньше было встречено x, ни один из текущих путей не может помочь другому кратчайшему пути. Поскольку x встречается раньше, все пути, которые могут следовать, будут по крайней мере на один длиннее предыдущего кратчайшего пути. Следовательно, ни один из этих путей не может способствовать сумме.

Это означает, однако, что мы встречаемся с каждым node не чаще одного раза и выполняем. Так что нормальная BFS просто отлично.

• Нам даже не нужно знать уровень, вместо этого мы можем получить окончательное число, как только встретимся с окончательным node.

Это можно скомпилировать в очень простой алгоритм, который в основном просто BFS.

 - Mark nodes as visited as usual with BFS.
 - Instead of adding just nodes to the queue in the DFS add nodes plus number of incoming paths.
 - If a node that has been visited should be added ignore it.
 - If you find a node again, which is currently in the queue, do not add it again, instead add the counts together.
 - Propagate the counts on the queue when adding new nodes.
 - when you encounter the final, the number that is stored with it, is the number of possible paths.

Ответ 2

Ваш алгоритм разбивается на график, подобный

  *   *   *   1
 / \ / \ / \ / \
v   *   *   *   w
 \ / \ / \ / \ /
  *   *   *   2

со всеми ребрами, направленными слева направо. Он рассчитывает два пути: один через 1, а другой через 2, но как 1, так и 2 может быть достигнут с v на восемь разных кратчайших путей, в общей сложности шестнадцать.

Ответ 3

Как показывает qrqrq, ваш алгоритм терпит неудачу на некоторых графиках, но идея BFS хороша. Вместо этого сохраните массив z размера |V|, который вы инициализируете до нуля; сохраните количество кратчайших путей в обнаруженной вершине i на расстоянии менее level в z[i]. Также поддерживайте массив d размера |V| таким образом, что d[i] - это расстояние от v до вершины i, если это расстояние меньше level. Инициализируйте level до 0, d[v] до 0 и z[v] до 1 (существует один путь длины от 0 до v до v) и установите все остальные записи d в -1 и от z до 0.

Теперь, когда вы сталкиваетесь с ребром от i до j в вашей BFS, тогда:

• Если d[j] = -1, установите d[j] := level и z[j] := z[i].
• Если d[j] = level, установите z[j] := z[j] + z[i].
• В противном случае ничего не делать.

Причина в том, что для каждого кратчайшего пути от v до i существует один самый короткий путь от v до j. Это даст количество кратчайших путей от v до каждой вершины в линейном времени. Теперь сделайте то же самое, но начиная с w.

Ответ 4

Этот алгоритм выглядит корректно для меня.

BFS, как вы знаете, является поиском линейного времени (O(N)), потому что время T, необходимое для его завершения, в худшем случае T = C + a * N, где N - количество узлов и C, a - любые фиксированные константы.

В вашем случае выполнение поиска дважды - сначала от v до w, а затем от w до v - (в худшем случае) 2T или 2C + 2a * N, что также удовлетворяет линейное требование времени O(N), если вы определяете новый C' = 2C и новый a' = 2a, потому что оба C' и a' также являются фиксированными константами.

Ответ 5

Могу ли я сделать это таким образом

• Я перемещаюсь с помощью BFS, пока не дойду до конечной вершины и не поддерживаю уровни
• Как только я достиг целевого уровня, я использую таблицу уровней следующим образом

Из таблицы уровней я начинаю обратный отсчет числа родителей до вершины на нашем пути (первый раз это была бы конечная вершина).
 На каждом шаге я умножаю число отдельных родителей, найденных на этом конкретном уровне, на кратчайшие пути, которые у меня могут быть до конечной вершины.
Я поднимаюсь вверх по уровням, только учитывая узлы, которые попадают в мой путь и умножают количество разных родителей, найденных на каждом уровне, до тех пор, пока я не достиг уровня 0.

Это работает?

Ответ 6

int edgeCb( graphPT g, int x, int y )
{
    if ( dist[ y ] > dist[ x ] + 1 ) {
        dist[ y ] = dist[ x ] + 1; // New way
        ways[ y ] = ways[ x ]; // As many ways as it parent can be reached
    } else if ( dist[ y ] == dist[ x ] + 1 ) {
        ways[ y ] += ways[ x ]; // Another way
    } else {
        // We already found a way and that is the best
        assert( dist[ y ] < g->nv );
    }
    return 1;
}

Выше кода дает мне правильные результаты для всех типов графиков, упомянутых в этом сообщении. В основном это обратный вызов для обхода BFS.

dist [start] = 0; пути [start] = 1;

для всех вершин dist [x] = numberOfVertices;//Это выходит за максимальное возможное отключение

BFS (g, начало);

Если пути [end] не равны нулю, то это число путей, а dist [end] представляет кратчайшее расстояние.

Включение путей [конец] == 0 означает, что конец не может быть достигнут с самого начала.

Пожалуйста, дайте мне знать, если в этом есть какие-либо дыры в петле.

Ответ 7

Простейшее решение, изменяя BFS:

count (v) = 0, count (s) = 1. для каждого соседа u of v, если (d (v) + 1 == d (u)), то count (u) + = count (v). теперь reset все и делать то же самое из конечной вершины.