Беллмана-Форда со списком смежности (кратчайший путь с отрицательными весами)
Я реализую свою собственную версию алгоритма Беллмана-Форда для поиска кратчайших путей с отрицательными весами. Однако я не уверен, правильно ли это, поскольку, по моему мнению, сложность моего решения отличается от широко принятой сложности Беллмана-Форда O(|V||E| + |E|) = O(|V|| Е |).
Для этого я использую массив списков смежности A для каждой вершины k графа. Каждый элемент в списке смежности для вершины k, elem имеет два элемента данных elem->vertex, соответствующие ребру (k, elem->vertex) и весу elem->weight того же ребра. iS — начальный узел, iT — конечный узел.
Я упростил алгоритм, чтобы просто возвращать кратчайшее расстояние от iS до iT.
Bellman_Ford(A,iS,iT):
d <- new Array(A.size(),∞) // Distance array to vertex iS
d[iS] <- 0
for i <- 1 to A.size() - 1:
for k <- 0 to A.size() - 1:
for elem in A[k]:
if d[k] + elem->weight < d[elem->vertex]:
d[elem->vertex] <- d[k] + elem->weight
for k <- 0 to A.size() - 1:
for elem in A[k]:
if d[k] + elem->weight < d[elem->vertex]:
throw "Negative cycle found"
return d[iT] // if iT not reachable by iS will return ∞
Из-за списка смежности мне кажется, что сложность заключается в следующем: O(|V|(|V|+|E|) для первой группы вложенных циклов и O(|E|) для поиска отрицательного цикла, при общей сложности:
O(|V|(|V|+|E|) + |E|) = O(|V|² + |V||E| + |E|) = O(|V|² + |V|| Д|)
Можете ли вы добавить свой код реализации, чтобы мы увидели?
@user24714692 user24714692 Реализация уже существует: будь то в псевдокоде или на любом другом языке, это не изменит асимптотическое поведение (алгоритмическую сложность), и поэтому я хочу, чтобы она оставалась независимой от языка.
@Unmitigated: Я понимаю, откуда вы пришли, но упрощение возможно только наоборот: |V|^2 всегда будет доминировать |E|, поскольку для самого большого |E| |V|^2 будет по крайней мере, одинаково большой. Другими словами, для моего термина, если мы явно не имеем дело с полным графом (что не обязательно), мы не можем упростить больше, чем O(|V|^2 + |V||E|)
Я имел в виду временную сложность наихудшего случая, которую часто рассматривают при обсуждении большого О. Но да, стандартный алгоритм Беллмана-Форда полагается на предварительное наличие списка ребер; использование списка смежности не будет тем же самым.
@Unmitigated Это ответ, который я искал :) Если хотите, вы можете опубликовать его как ответ, возможно, с некоторой ссылкой на прошлый вопрос или статью, подтверждающую это утверждение, и я отмечу его как официальный ответ.
Ответы 1
Ваш анализ верен, но он приводит только к еще большей сложности — по сравнению со стандартной сложностью Ө(|V||E|) — когда граф имеет значительно меньше ребер, чем вершин (и, как следствие, не является связным).). В этом случае ваша реализация имеет временную сложность Ө(|V|²), что хуже стандартной Ө(|V||E|). Но когда это не так, т.е. когда |E| есть Ω(|V|), то Ө(|V|² + |V||E|) есть Ө(|V||E|).
Если вас интересуют графы с относительно небольшим количеством ребер, вы можете адаптировать свою реализацию, чтобы избежать посещения вершин, не имеющих исходящих ребер. Например, вы можете собрать k, для которого A[k] не пусто, в вектор, а затем использовать этот вектор в основном алгоритме:
Bellman_Ford(A, iS, iT):
// Collect vertices that have outgoing edge(s)
connected ← new Vector()
for k ← 0 to A.size() - 1:
if A[k].size() > 0:
connected.add(k);
d ← new Array(A.size(), ∞) // Distance array to vertex iS
d[iS] ← 0
for i ← 1 to A.size() - 1:
// Now this loop is guaranteed to make at most |E| iterations:
for j ← 0 to connected.size() - 1:
k = connected[j]
for elem in A[k]: // Now guaranteed to make at least one iteration
if d[k] + elem->weight < d[elem->vertex]:
d[elem->vertex] ← d[k] + elem->weight
// And you might as well use the same approach here:
for j ← 0 to connected.size() - 1:
k = connected[j]
for elem in A[k]:
if d[k] + elem->weight < d[elem->vertex]:
throw "Negative cycle found"
return d[iT] // if iT not reachable by iS will return ∞
Большое спасибо! Несвязанный вопрос: как вам удалось раскрасить свой алгоритм? Когда дело доходит до синтаксиса, он кажется эквивалентным моему.
Я пометил блок кода языком. Итак, три обратных знака, за которыми следует cpp или java или любой другой язык.
Обратите внимание, что |E| может быть O(|V|^2) (в почти полном графе), так что |V||E| будет доминировать |V|^2.