Подсчитывает количество кратчайших путей, проходящих через дугу (u, v).

Дан ориентированный взвешенный граф с вершиной ппg> и дугой м (п <1500, м <5000) и одной дугой (u, v). И ответьте на вопрос, сколько кратчайших путей (может начинаться в любой позиции а и заканчиваться на б, так что а! = b) проходит через заданную дугу.

Пример:
п = 4, м = 4БРР444 дуга (1, 2) массой 5БРР444 дуга (2, 3) массой 5БРР444 дуга (3, 4) массой 5БРР444 дуга (1, 4) массой 8БРР444 и дуга (1, 2) .
Ответ - 2, потому что дуга (1, 2) на кратчайшем пути 1-> 3 и 1-> 2.

Дийкстра может решить эту проблему?

Я голосую за то, чтобы закрыть этот вопрос как не по теме, потому что он касается теоретической информатики.

Lennart 05.11.2018 13:49
3
1
984
2

Ответы 2

Одна быстрая мысль: поскольку все дело в реконструкции пути, вы можете использовать Floyd-Warshall's algorithm для поиска кратчайшего пути между каждой парой узлов гораздо более дешевым способом по сравнению с запуском Dijkstra's algorithm для каждого узла. После этого, выполняя реконструкцию пути для каждого узла, вы просто проверяете, существует ли указанная дуга на найденном пути. (Обратите внимание, однако, что алгоритм Флойда-Уоршалла не поддерживает графики с отрицательными циклами)

вы также можете добавить флаг к ребрам, сначала пересекающим дугу, чтобы обход мог напрямую выдать желаемый результат

rvalue 01.11.2018 04:10

Сначала найдите кратчайший путь между u и v с помощью алгоритма Дейкстры. Интересно, что если кратчайший путь между u и v не является ребром uv, то ни один кратчайший путь между любыми двумя точками никогда не будет содержать ребро uv. В таком случае вы можете отправить свой ответ как 0.

Теперь мы можем приступить к применению Алгоритм Флойда УоршаллаO(n^3) один раз или Алгоритм Дейкстры с использованием кучи ФибоначчиO(m+n*logn) на каждом узле, что в сумме будет O(n*m + (n^2)*logn). Обычно я бы рекомендовал Флойда Уоршалла, но поскольку максимальное значение m не похоже на порядок n ^ 2 для максимального значения n, алгоритм Дейкстры на нескольких узлах может стать жизнеспособным, если вы используете кучу Фибоначчи. (m и n могут быть достаточно большими, чтобы компенсировать огромные константы при использовании последних.)

Следующий,

From every point "a" see if shortest path length to "u" + len(u->v) + shortest path length from "v" to "b" is = shortest path length from "a" to "b". This should take constant time for every check since we already have a table of the shortest paths. That'll come out to be the order of n choose 2 that is O(n^2)

Для всех a и b, где это правда, вам нужно выяснить, существует ли несколько кратчайших путей. Это будет болью. Ни алгоритм Дейкстры, ни алгоритм Флойда Уоршалла не дают вам способа найти кратчайшие пути все между любыми двумя точками. Они гарантируют только кратчайший путь а. Одним из способов грубой силы может быть определение одного кратчайшего пути и изменение одного края за раз, чтобы увидеть, появится ли новый кратчайший путь!

Весь этот процесс должен быть быстрее, чем построение всех возможных путей, проверка того, является ли он самым коротким, и, наконец, проверка того, проходит ли он через требуемое ребро. Однако я очень хочу узнать, можно ли оптимизировать или изменить последнюю часть моего предписанного алгоритма.

Редактировать: Поскольку известно, что график является направленным ациклическим графиком, нет необходимости применять Bellman ford в начале. Если вы хотите узнать, как идентифицируются циклы отрицательного веса ребер в ориентированных графах, прочтите, пожалуйста, о Алгоритм Джонсона.

Окей. Спасибо большое. Я это протестирую.

Nguyễn Văn 04.11.2018 18:28

Но могу ли я использовать dijkstra, чтобы найти кратчайший путь, я использую расстояние массива [u] от x до u. Это DAG, и я нахожу номера кратчайшего пути к u (до [u]) и номера кратчайшего пути от v (от [v]), результат становится к [u] * от [v]? Это верно?

Nguyễn Văn 04.11.2018 18:32

Да, это идея. Но сделайте это только после проверки того, что длина кратчайшего пути (от x до u) + (от u до v) + (от v до y) действительно равна кратчайшему пути (от x до y). В противном случае u, v никогда не попадут на кратчайший путь между x и y.

101010acity 04.11.2018 21:41

Другие вопросы по теме