Negative Edge Costs Shortest-Path

The following algorithm borrows the idea from 202204151055 and 202204151059 to calculate the shortest path in a graph with negative edge costs.

Analysis

• It will result in \(O(\vert E \vert \cdot \vert V \vert)\)

Attention

• To get out from the negative-cost cycle#, stop the algorithm after any vertex has dequeued \(\vert V \vert + 1\) times could solve the problem.

Implementation

void WeightedNegative(Table T)
{
  Queue Q;
  Vertex V, W;

  Q = CreateQueue(NumVertex);
  MakeEmpty(Q);
  Enqueue(S, Q);

  while (!IsEmpty(Q)) {
    V = Dequeue(Q);
    
    for each W adjacent to V
      if (T[V].dist + Cvw < T[W].Dist) {  // Cvw: the weight for edge (v,w)
        T[W].Dist = T[V].Dist = Cvw;
        T[W].Path = V;
        if (W is not already in Q)
          Enqueue(W, Q);
      }
  }

  DisposeQueue(Q);
}