我正在看。
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
// part 1
for each vertex v
dist[v][v] ← 0
// part 2
for each edge (u,v)
dist[u][v] ← w(u,v) // the weight of the edge (u,v)
// part 3
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
所以我来到了这个美丽的问题,它要求你写一个程序,找出在有向图中是否存在负无穷短路径。(也可以认为是查找图中是否存在“负循环”)。下面是这个问题的链接:
我成功地解决了这个问题,我从图中的任何源开始,运行了两次Bellman Ford算法。第二次运行算法时,我检查节点是否可以松弛。如果是这样,那么在图中肯定有一个负循环。下面是我的C++代码:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int test;