c++ - 有两个变量的最短路径

Question

因此，我尝试使用修改后的 Bellman Ford 算法来查找从起始顶点到结束顶点的最短路径，但我无法超过一定距离。所以给定一个有边的图:

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;
}

求助!这可能并不难，但决赛让我压力很大

Answer 1

这个问题被称为“受约束的最短路径” 问题，比这更难解决。您提供的算法没有解决它，它只是可能根据图表的结构找到解决方案，靠运气。

当此算法应用于您提供的图表时，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)的路径。如您所见，节点 2 已找到路径 0-->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

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

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