Dijkstra - 在预算范围内找到目的地
Dijkstra - find destinations within budget
我得到了一张图，其中包括一个起始顶点、其他顶点，以及表示从一个顶点到另一个顶点的成本的边。我需要找到我可以从起始顶点前往的目标顶点集。预算是一定数额的美元，旅行总费用应该在预算之内。我如何对这个问题实施 Dijkstra 算法？我想我们以前通常使用Dijkstra来寻找两个固定顶点之间的最短路径。但是我不确定如何在这个预算问题上实施 Dijkstra。如果有人可以提供一些想法，那真的很有帮助！
据我了解，Dijkstra 算法解决了 single-source shortest path 问题。这意味着生成的数据结构是一棵以起始节点为根的树。通常，一个实现会存储从起始节点到达每个节点的最小成本。总的来说，在预算内可以到达的顶点集是最短路径成本不超过预算的顶点集。算法本身不需要修改；在附加步骤中，必须将预算范围内可以到达的节点作为输出返回。
如果你使用 Dijkstra 算法，你可能会遇到以下情况：
假设预算为 50，图表有 4 个节点（开始、节点 1、节点 2、节点 3）
开始节点 -> 节点 1 (15) -> 节点 2 (10)：因此总成本为 25
起始节点 -> 节点 3 (15)：总成本为 15
那么现在您的预期结果是什么？你应该去节点 1 然后去节点 2 并忽略节点 3（因为你不能 return 返回开始然后去节点 3，return 也将花费 30）。或者你应该去节点1，回到开始，然后去节点3（总成本45，你可以利用的最大成本）
你需要的不是覆盖所有目的地的最短路径是Floyd-Warshall算法https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm
我得到了一张图，其中包括一个起始顶点、其他顶点，以及表示从一个顶点到另一个顶点的成本的边。我需要找到我可以从起始顶点前往的目标顶点集。预算是一定数额的美元，旅行总费用应该在预算之内。我如何对这个问题实施 Dijkstra 算法？我想我们以前通常使用Dijkstra来寻找两个固定顶点之间的最短路径。但是我不确定如何在这个预算问题上实施 Dijkstra。如果有人可以提供一些想法，那真的很有帮助！
据我了解，Dijkstra 算法解决了 single-source shortest path 问题。这意味着生成的数据结构是一棵以起始节点为根的树。通常，一个实现会存储从起始节点到达每个节点的最小成本。总的来说，在预算内可以到达的顶点集是最短路径成本不超过预算的顶点集。算法本身不需要修改；在附加步骤中，必须将预算范围内可以到达的节点作为输出返回。
如果你使用 Dijkstra 算法，你可能会遇到以下情况：
假设预算为 50，图表有 4 个节点（开始、节点 1、节点 2、节点 3）
开始节点 -> 节点 1 (15) -> 节点 2 (10)：因此总成本为 25
起始节点 -> 节点 3 (15)：总成本为 15
那么现在您的预期结果是什么？你应该去节点 1 然后去节点 2 并忽略节点 3（因为你不能 return 返回开始然后去节点 3，return 也将花费 30）。或者你应该去节点1，回到开始，然后去节点3（总成本45，你可以利用的最大成本）
你需要的不是覆盖所有目的地的最短路径是Floyd-Warshall算法https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm