Кратчайшие пути быстрее - алгоритм SPFA?

Question

Я реализую алгоритм k-кратчайших вершинно-непересекающихся путей и мне нужен быстрый алгоритм поиска кратчайшего пути. Есть отрицательные веса, поэтому я не могу используйте дейкстра и беллман-форд это O (ne). В статье я читал недавно авторов использовал так называемый алгоритм SPFA для нахождения кратчайшего пути в графе с отрицательный вес, который - по их мнению - имеет сложность O (е). Звуки интересно, но я не могу найти информацию об алгоритме. Appearently это: http://en.cnki.com.cn/Article_en/CJFDTOTAL-XNJT402.015.htm оригинал бумага, но у меня нет к ней доступа.

У кого-нибудь есть хорошая информация или, возможно, реализация этого алгоритма? Кроме того, есть ли какой-нибудь источник проблемы k-кратчайших вершинно-непересекающихся путей? Я ничего не могу найти.

Спасибо!

Answer 1

Алгоритм SPFA - это оптимизация по Беллману-Форду.В то время как в Bellman-Ford мы просто вслепую проходим каждый край для | V |раунды, в SPFA, очередь поддерживается, чтобы убедиться, что мы проверяем только те расслабленные вершины.Идея похожа на Дейкстры.Он также похож на BFS, но узел может быть помещен в очередь несколько раз.

Источник сначала добавляется в очередь.Затем, пока очередь не пуста, из очереди извлекается вершина u, и мы смотрим на всех ее соседей v. Если расстояние v изменяется, мы добавляем v в очередь (если она уже не находится в очереди).

Автор доказал, что SPFA часто быстрая (\ Theta (k | E |), где k <2). </p>

Вот псевдокод из Википедия на китайском языке , где вы также можете найти реализацию в C.

Procedure SPFA;
Begin
  initialize-single-source(G,s);
  initialize-queue(Q);
  enqueue(Q,s);
  while not empty(Q) do 
    begin
      u:=dequeue(Q);
      for each v∈adj[u] do 
        begin
          tmp:=d[v];
          relax(u,v);
          if (tmp<>d[v]) and (not v in Q) then
            enqueue(Q,v);
        end;
    end;
End;

Answer 2

На самом деле это хороший алгоритм для определения кратчайшего пути. Он также считается алгоритмом Беллмена-Форда, переписанным очередью. Но, на мой взгляд, ему нравится BFS. Сложность его - O (ke) (e означает число ребер, k ≈ 2). Несмотря на то, что я вообще не могу этого понять, оно быстро в большинстве задач, особенно когда ребер всего несколько.

Func spfa(start, to) {
  dis[] = {INF}
  visited[] = false 
  dis[start] = 0
  // shortest distance
  visited[start] = true 
  queue.push(start)
  // push start point
  while queue is not empty {
    point = queue.front()
    queue.pop()
    visited[point] = false
    // marked as unvisited                    
    for each V from point {
      dis[V] = min(dis[V],dis[point] + length[point, V]);
      if visited[V] == false {
        queue.push(V)
        visited[V] = true
      }
    }
  }
  return dis[to]
}

Это также очень легко найти путь и многое другое Надеюсь, я могу помочь вам (● - ●) От OIer