2

所以我试图使用修改后的贝尔曼福特算法来找到从起始顶点到结束顶点的最短路径，但我不能超过一定的距离。所以给定一个带边的图：

0 1 100 30
0 4 125 50
1 2 50 250 
1 2 150 50 
4 2 100 40 
2 3 90 60 
4 3 125 150

其中每条线代表一条边，第一个值是起始顶点，第二个值是结束顶点，第三个是成本，第四个是距离。使用我现在拥有的代码，当我尝试找到从 0 到 3 的最便宜路径而不超过 140 时，它会产生 0（未找到路径时的默认值）而不是 340（最便宜路径的成本）。有关如何更改我的代码的任何建议。

只需将代码复制到下面，因为该站点不允许我做任何其他事情。

 static void BellmanFord(struct Graph *graph, int source, int ending, int max){

 int edges = graph->edgeCount;
 int vertices = graph->verticesCount;
 int* money = (int*)malloc(sizeof(int) * vertices);
 int* distance = (int*)malloc(sizeof(int) * vertices);

 for (int I = 0; I < vertices; I++){
       distance[I] = INT_MAX;
       money[I] = INT_MAX;
  }
  distance[source] = 0;
  money[source] = 0;

 for (int I = 1; I <= vertices - 1; ++I){
      for int j = 0; j < edges; ++j){
           int u = graph->edge[j].Source;
           int v = graph->edge[j].Destination;
           int Cost = graph->edge[j].cost;
           int Duration = graph->edge[j].duration;

           if ((money[u] != INT_MAX) && (money[u] + Cost < money[v])){
               if (distance[u] + Duration <= max){
                    money[v] = money[u] + Cost;
                    distance[v] = distance[u] + Duration;
                }
           }
      }
  }

  if (money[ending] == INT_MAX) cout << "0" << endl;
  else cout << money[ending] << endl;
}

请帮忙！这可能不是那么难，但决赛让我压力山大

4

2 回答 2

0

这个问题，被称为“受约束的最短路径”问题，比这更难解决。您提供的算法不能解决它，它只能根据图形的结构抓住解决方案，只能靠运气。

当将此算法应用于您提供的图时max-distance = 140，它无法找到解决方案，即0-->1-->2-->3（使用边1 2 150 50）总成本为 340，距离为 140。

我们可以通过在节点更新时记录更新来观察失败的原因，结果如下：

from node       toNode      newCost      newDistance

0                1              100          30

0                4              125          50

1                2              250          80

4                2              225          90

在这里，算法被卡住了，不能走得更远，因为从这一点开始的任何进展都会导致路径超过最大距离（140）。如您所见，节点 20-->4--2在遵守最大距离约束的情况下找到了从节点 0 成本最低的路径。但是现在，从 2 到 3 的任何进展都将超过 140 的距离（它将是 150，因为 2->3 的距离为 60。）

再次运行max-distance=150将找到路径 0-->4->3，成本为 315，距离为 150。

from node       toNode      newCost      newDistance

0                1              100          30

0                4              125          50

1                2              250          80

4                2              225          90

2                3              315         150

显然，这不是尊重距离约束的最小成本路径；在第一个示例中，正确的应该是相同的（它未能找到）。这再次证明了算法的失败；这次它给出了一个解决方案，但这不是最佳解决方案。

总之，这不是代码中的编程错误或错误，只是算法不足以解决所述问题。

于 2016-12-04T08:18:24.520 回答
0

好的，就在之前

if (money[ending] == INT_MAX) cout << "0" << endl;

我添加了一些使其工作的代码，但我想知道这是否适用于每种情况，或者是否需要进行一些更改。

   if (money[ending] == INT_MAX){
       for (int j = 0; j < edges; ++j){
             int u = graph->edge[j].Source;
             int v = graph->edge[j].Destination;
             int Cost = graph->edge[j].cost;
             int Duration = graph->edge[j].duration;

             if ((distance[u] != INT_MAX) && (distance[u] +Duration < distance[v])){
                 if (distance[u] + Duration <= max){
                      money[v] = money[u] + Cost;
                       distance[v] = distance[u] + Duration;
                  }
             }
       }
 }
于 2016-12-04T17:05:16.303 回答