C# 中的贝尔曼福德:始终返回负循环.我错过了什么吗?

Question

这是影响：

如果没有负循环，则返回 true

public static bool ShortestPaths(Graph graph, int vStart,
out double[] pi, out int[] pred)
{
int V = graph.Nodes();
pi = new double[V];                 //shortest known path lengths
pred = new int[V];                  //predeceesor nodes for these paths
for (int v = 0; v < V; v++){
// TODO: Here we need to initialize pi and pred.
pi[v] = System.Double.PositiveInfinity;
pred[v] = -1;
}
pi[vStart] = 0;
List<Edge> edges = graph.AllEdges();
// Apply the inner loop once for every node.
for (int v = 0; v < V; v++)
{   
foreach (Edge edge in edges)    //test edges all edges
{
// TODO: In this inner loop we need to update
//       pi and pred.
int w = edges[v].To();
double weight = edges[v].Weight();
if (pi[v] + weight < pi[w]) { 
pi[w] = pi[v] + weight;
pred[w] = v; 
}
}
}

测试是否存在负循环并返回假 如果存在这样的循环。

List<Edge> bedges = graph.AllEdges();
foreach (Edge edge in bedges) {
int w = edge.To();
int v = edge.From();
double weight = edge.Weight();
if (pi[v] + weight < pi[w]) {
return false;
}
}
return true;
}

图形看起来像这样：(v，w，weigth(

int[,] edges = 
{{0,1,3},{0,2,2},{0,3,3},{1,0,8},{1,3,2},{1,4,1},{2,0,7},{2,5,2},{2,6,7},
{3,0,6},{3,1,3},{3,4,2},{3,5,3},{3,6,4},{4,1,1},{4,3,3},{4,6,1},{5,2,3},
{5,3,3},{5,6,3},{6,3,3},{6,4,1},{6,2,7},{6,5,4}};

这其中没有负 int，但它会返回 false。

Answer 1

你的放松步骤中有一个错误：

外部循环指定顶点v。

您的内部循环指定边e。

在内部循环中，您每次迭代都会反复采用边v，而不是考虑边e来填充pi和pred数组。

您可以按如下方式修复它：

for (int v = 0; v < V; v++)
{   
foreach (Edge edge in edges)    //test edges all edges
{
int from = edge.From();
int to = edge.To();
double weight = edge.Weight();
if (pi[from] + weight < pi[to]) { 
pi[to] = pi[from] + weight;
pred[to] = from; 
}
}
}