如何在至少通过某些节点一次的条件下找到最便宜的遍历路径
How to find the cheapest traversal path with condition of passing certain nodes at least once
我有一个听起来像这样的问题：
- 你在一片危险的森林里。每次使用时，您选择的每条路径都有一定的风险。 （具有评估边的无向图）。你的任务是从入口进入宝藏洞，然后从出口逃走（在与入口不同的地方）
为此，我假设我需要使用 Dijkstra 算法来找到从 A（开始）到 B，然后从 B（trasure）到 C（退出）的最便宜路径。
第二个问题我不知道怎么办..
- 考虑同样的问题，但是有 5 个 gem 散落在森林的十字路口（节点）上，并且有一只致命的狼在睡觉，如果你收集一个 gem 它会杀了你在先杀死他之前。你必须在离开森林之前收集所有 5 个。
我不确定如何将 Dijkstra 算法应用于此。我知道我首先必须应用 Dijsktra 的算法才能到达狼的节点，同时假装具有 gems 的节点及其边缘不存在，但是我不确定通往 B 的最便宜的路径是什么C 同时收集所有 gem 可能位于更昂贵路径上的所有
虽然我可以 运行 5 个 Dijsktra 实例分别获得每个 gem 的最便宜路径。我意识到可能存在这样一种情况，即两条最便宜路径的总和 gems 最终可能不仅仅是走一条更短更昂贵的路径来同时抓住它们
示例（忽略箭头）：
如果gem_1在节点2，gem_2在节点1，我会先找到最便宜的路径到gem_1，然后到gem_2，这比在 gem_1.
之前访问 gem_2 更贵
我是否必须对访问节点的所有顺序进行排列，并且 运行 Dijsktra 会针对每个要收集的 gem 的不同顺序进行迭代？或者，还有更好的方法？还有其他我应该注意的事情吗？
让我们忽略狼的事实，因为您知道如何处理它并重新表述问题以便获得更多关注：您有一个包含源和目标的图，并且您必须访问其他五个节点（称为 gems).
所以要做的第一件事是 运行 来自源和 gems 的 SSSP 算法（比方说 Dijkstra），这样你将在源之间获得最小距离，每个 gem 和目的地。
通过这种方式，您可以看到一个新的全连接图，其中源、目标和 gems 是节点，之前计算的距离是边权重。在此图中，您必须探索具有起始节点和结束节点的每个节点。我认为这是旅行商问题的一个特殊版本，但是你只有 7 个节点，所以你可以尝试所有的可能性
我会做以下建模：
- 按照@Marco Zamboni 的提议，首先找到狼，同时认为宝石的所有边都不存在。
- 做一个Dijkstra（开始节点：wolf，结束节点：exit），同时忽略所有边退出，只要你还没有收集到所有宝石。
如果能提供测试用的图表就更好了。
我有一个听起来像这样的问题：
- 你在一片危险的森林里。每次使用时，您选择的每条路径都有一定的风险。 （具有评估边的无向图）。你的任务是从入口进入宝藏洞，然后从出口逃走（在与入口不同的地方）
为此，我假设我需要使用 Dijkstra 算法来找到从 A（开始）到 B，然后从 B（trasure）到 C（退出）的最便宜路径。
第二个问题我不知道怎么办..
- 考虑同样的问题，但是有 5 个 gem 散落在森林的十字路口（节点）上，并且有一只致命的狼在睡觉，如果你收集一个 gem 它会杀了你在先杀死他之前。你必须在离开森林之前收集所有 5 个。
我不确定如何将 Dijkstra 算法应用于此。我知道我首先必须应用 Dijsktra 的算法才能到达狼的节点，同时假装具有 gems 的节点及其边缘不存在，但是我不确定通往 B 的最便宜的路径是什么C 同时收集所有 gem 可能位于更昂贵路径上的所有
虽然我可以 运行 5 个 Dijsktra 实例分别获得每个 gem 的最便宜路径。我意识到可能存在这样一种情况，即两条最便宜路径的总和 gems 最终可能不仅仅是走一条更短更昂贵的路径来同时抓住它们
示例（忽略箭头）：
如果gem_1在节点2，gem_2在节点1，我会先找到最便宜的路径到gem_1，然后到gem_2，这比在 gem_1.
之前访问 gem_2 更贵我是否必须对访问节点的所有顺序进行排列，并且 运行 Dijsktra 会针对每个要收集的 gem 的不同顺序进行迭代？或者，还有更好的方法？还有其他我应该注意的事情吗？
让我们忽略狼的事实，因为您知道如何处理它并重新表述问题以便获得更多关注：您有一个包含源和目标的图，并且您必须访问其他五个节点（称为 gems).
所以要做的第一件事是 运行 来自源和 gems 的 SSSP 算法（比方说 Dijkstra），这样你将在源之间获得最小距离，每个 gem 和目的地。
通过这种方式，您可以看到一个新的全连接图，其中源、目标和 gems 是节点，之前计算的距离是边权重。在此图中，您必须探索具有起始节点和结束节点的每个节点。我认为这是旅行商问题的一个特殊版本，但是你只有 7 个节点，所以你可以尝试所有的可能性
我会做以下建模：
- 按照@Marco Zamboni 的提议，首先找到狼，同时认为宝石的所有边都不存在。
- 做一个Dijkstra（开始节点：wolf，结束节点：exit），同时忽略所有边退出，只要你还没有收集到所有宝石。
如果能提供测试用的图表就更好了。