使用最短路徑快速演算法檢測圖中的負環

---

最短路徑快速演算法是 Bellman-Ford 演算法的改進或更最佳化的版本。它計算加權有向圖中單個源的最短路徑。此演算法特別適用於具有負權邊重的圖。

演算法

給定一個加權有向圖和一個源頂點，演算法找到從到圖中每個頂點 的最短路徑。從到 的最短路徑長度儲存在每個頂點的 中。

procedure Shortest-Path-Faster-Algorithm(G, s)
   for each vertex v ≠ s in V(G)
      d(v) := ∞
   d(s) := 0
   push s into Q
   while Q is not empty do
      u := poll Q
      for each edge (u, v) in E(G) do
         if d(u) + w(u, v) < d(v) then
            d(v) := d(u) + w(u, v)
            if v is not in Q then
               push v into Q

問題陳述

給定一個包含 N 個節點的圖 G，節點值從 0 到 N-1，一個源 S 和一個型別為 {u, v, w} 的陣列 A[][3]，表示從 u 到 v 的一條權重為 w 的有向邊。目的是找出從給定源開始，圖中是否存在負環。

示例 1

Input: N = 3, S = 0, A[][] = {{0, 1, -2}, {1, 2, 1}, {2, 0, -1}}
Output: True

解釋

從 0 開始，圖包含以下迴圈：

0 -> 1 -> 2 -> 0

上述迴圈的權重總和 = (-2) + 1 + (-1) = (-2)

因此，圖包含負權迴圈。

示例 2

Input: N = 3, S = 0, A[][] = {{0, 1, -2}, {1, 2, 1}, {0, 2, -1}}
Output: False

解釋

從 0 開始，圖不包含迴圈。

解決方案方法

使用 SPFA 檢測圖中的負權迴圈，我們遵循以下步驟：

• 建立陣列 distance[]，其值為無窮大，visited[]，其值為 false，以及 count[]，其值為 0，它將包含節點被鬆弛的次數。

• 然後使用 SPFA 演算法遍歷圖。

• 在鬆弛（即更新連線到 v 的每個頂點的成本，如果透過在路徑中包含 v 來改進成本）時，為每個頂點遞增計數。

• 如果某個頂點被鬆弛了 N 次，則返回 true，否則返回 false。

示例：C++ 實現

以下程式碼使用 SPFA 演算法查詢圖中的負環。

#include <bits/stdc++.h>
using namespace std;

bool SFPA(int V, int S, int E[][3], int M){
   // Adjacency list of the given graph
   vector<pair<int, int>> g[V];
   // Create Adjacency List
   for (int i = 0; i < M; i++){
      int u = E[i][0];
      int v = E[i][1];
      int w = E[i][2];
      g[u].push_back({v, w});
   }
   vector<int> distance(V, INT_MAX);
   vector<bool> visted(V, false);
   vector<int> count(V, 0);
   // Distance from src to src is 0
   distance[S] = 0;
   queue<int> q;
   q.push(S);
   // Mark source as visited
   visted[S] = true;
   while (!q.empty()) {
      int u = q.front();
      q.pop();
      visted[u] = false;
      // Relaxing all edges of vertex from the Queue
      for (pair<int, int> x : g[u]) {
         int v = x.first;
         int cost = x.second;
         // Update the distance[v] to minimum distance
         if (distance[v] > distance[u] + cost) {
            distance[v] = distance[u] + cost;
            // If vertex v is in Queue
            if (!visted[v]) {
               q.push(v);
               visted[v] = true;
               count[v]++;
               // Negative cycle
               if (count[v] >= V)
               return true;
            }
         }
      }
   }
   // No cycle found
   return false;
}
int main(){
   int N = 4;
   int S = 0;
   int M = 4;
   // Given Edges with weight
   int E[][3] = {{0, 1, 1},
   {1, 2, -1},
   {2, 3, -1},
   {3, 0, -1}};
   // If cycle is present
   if (SFPA(N, S, E, M) == true)
   cout << "True" << endl;
   else
   cout << "False" << endl;
   return 0;
}

輸出

True

結論

總之，為了檢測圖中的負環，可以使用最短路徑快速演算法，因為它在處理負權邊時效率最高。上述解決方案的時間複雜度為 O(N*M)，空間複雜度為 O(N)。