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

Question

Предположим, у меня есть ориентированный взвешенный граф с положительными или отрицательными весами (без нулевых или отрицательных взвешенных циклов). Граф анализируется Беллманом-Фордом, то есть каждая вершина содержит данные о самом легком пути к нему из исходной вершины и ее предшественнике по самому легкому пути. Каков наиболее эффективный способ хранения количества различных кратчайших путей от источника до каждой вершины? Я готов сделать это за линейное время - O(V+E), если это возможно.

Answer 1

Вы можете сделать это довольно эффективно, если у вас также нет отрицательных краев.

Пусть кратчайший путь к узлу v обозначаться как D(v)

сортировать вершины по расстояниям - O(VlogV)

обозначать P(v) - количество путей, ведущих от источника к v,
Теперь вы можете использовать DP для решения этого отношения (от первого до последнего):

P(source) = 1
P(v) = sum { P(u) | (u,v) is an edge and D(u) + w(u,v) = D(v) }

Сложность алгоритма O(VlogV + E)

Доказательство правильности: по индукции (рекомендации):
Базовое предложение для источника, существует один путь (пустой путь).
допустим, что P(v) корректно для каждого v такой, что D(v) < D(u),

Для каждого кратчайшего пути, который заканчивается uдолжно пройти одну из вершин так, чтобы D(v) < D(u), Учитывая кратчайший путь source->...->v->uпуть считается в P(v), Кроме того, он не учитывается для любых других P(v')так что он засчитывается ровно один раз в sum { P(u) | (u,v) is an edge and D(u) + w(u,v) = D(v) },
Кроме того, для любого пути, который не является кратчайшим путем, по предположению индукции, он не учитывается для любого пути. v такой, что D(v)<D(u), поэтому путь должен быть сгенерирован на последнем шаге, но ограничение (u,v) is an edge and D(u) + w(u,v) = D(v) препятствует этому, поэтому мы не учитываем кратчайший путь.
QED