使用最短路径快速算法检测图中的负环

最短路径快速算法是 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 算法查找图中的负环。

Open Compiler
#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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

结论

总之，为了检测图中的负环，可以使用最短路径快速算法，因为它在处理负权边时效率最高。上述解决方案的时间复杂度为 O(N*M)，空间复杂度为 O(N)。

更新于： 2023-10-25

170 次查看

开启您的 职业生涯

通过完成课程获得认证

开始
广告