dijkstra 在一条路径中最多有 10 个负边
dijkstra with at most ten negative edges in a path
作业中的一个问题，可能需要更改 Dijkstra 的实现或以某种方式减少。
设G=(V, E)，W为权重函数W：E->Z。
具有相同负值x的所有负权重边。 （例如，边上所有负权重的值为-10，其他均为正）
让我们定义"weight up to 10 negative edges,"哪个returns路径的权重，如果最多有十个负边，或者如果有十个以上负边，则为无穷大。
我需要找到一条从顶点 S 到所有其他顶点的 "weight up to 10 negative edges" 路径。
复杂度时间应该是O(Elog(V))或者O(E+Vlog(V))。
我想将图表复制十次，每次出现负权重边时，我们将从复制移动到下一个。我们将在第 10 次重复到第 11 次重复和 运行 Dijkstra 之间制作权重为无穷大的边，但我认为它不起作用。
应该有一个以某种方式使用 Dijkstra 的解决方案。
你不能使用带负权重的 Dijkstra 算法并得出正确的解决方案。请参阅 this 其他 post 以了解其失败的原因。
Dijkstra 算法不适用于负边，因为它迭代选择具有最短路径长度的 "unconfirmed" 节点，将其标记为 "confirmed"，然后从不更新该节点的路径长度再次。如果存在负边，则可能会在节点已经 "confirmed" 之后找到 "shorter" 路径，但如果该节点因此再次变为 "unconfirmed" 则可能可能是一个无限循环；同一个节点可以不断得到确认，然后一遍又一遍地取消确认，算法永远不会终止。为解决此问题而对算法所做的任何更改都必须解决该问题。
作为保证终止的一种方式，您可以记录一对像 (path length, # of negative edges) 而不是仅仅记录路径长度。当使用负边找到到 "confirmed" 节点的更短路径时，路径长度可能会变短，但该路径中的负边数会增加。因此，如果结果路径中的负边数大于 10，您可以编写一个条件来停止更新它。
不过，问题比这更微妙，因为节点的 "shortest path so far" 不再是最好保留的情况。假设您正在寻找一条从 A 到 C 的最短路径，最多使用 10 个负边，并且您找到了一条从 A 到 B 的长度为 10 且不使用负边的路径，而另一条从 A 到 B 的长度为 5 的路径使用了三个负边缘；您还不知道哪一个会导致更好的解决方案（或根本没有解决方案），因为从 B 到 C 的路径中可能有 8 个负边。因此，在每个节点，您不仅需要记录一对 (path length, # of negative edges)，你需要记录一组所有最好的这样的对。
希望这能让您了解如何调整 Dijkstra 算法来解决您的问题；还有一些细节需要您自己填写。
作业中的一个问题，可能需要更改 Dijkstra 的实现或以某种方式减少。
设G=(V, E)，W为权重函数W：E->Z。
具有相同负值x的所有负权重边。 （例如，边上所有负权重的值为-10，其他均为正）
让我们定义"weight up to 10 negative edges,"哪个returns路径的权重，如果最多有十个负边，或者如果有十个以上负边，则为无穷大。
我需要找到一条从顶点 S 到所有其他顶点的 "weight up to 10 negative edges" 路径。
复杂度时间应该是O(Elog(V))或者O(E+Vlog(V))。
我想将图表复制十次，每次出现负权重边时，我们将从复制移动到下一个。我们将在第 10 次重复到第 11 次重复和 运行 Dijkstra 之间制作权重为无穷大的边，但我认为它不起作用。
应该有一个以某种方式使用 Dijkstra 的解决方案。
你不能使用带负权重的 Dijkstra 算法并得出正确的解决方案。请参阅 this 其他 post 以了解其失败的原因。
Dijkstra 算法不适用于负边，因为它迭代选择具有最短路径长度的 "unconfirmed" 节点，将其标记为 "confirmed"，然后从不更新该节点的路径长度再次。如果存在负边，则可能会在节点已经 "confirmed" 之后找到 "shorter" 路径，但如果该节点因此再次变为 "unconfirmed" 则可能可能是一个无限循环；同一个节点可以不断得到确认，然后一遍又一遍地取消确认，算法永远不会终止。为解决此问题而对算法所做的任何更改都必须解决该问题。
作为保证终止的一种方式，您可以记录一对像 (path length, # of negative edges) 而不是仅仅记录路径长度。当使用负边找到到 "confirmed" 节点的更短路径时，路径长度可能会变短，但该路径中的负边数会增加。因此，如果结果路径中的负边数大于 10，您可以编写一个条件来停止更新它。
不过，问题比这更微妙，因为节点的 "shortest path so far" 不再是最好保留的情况。假设您正在寻找一条从 A 到 C 的最短路径，最多使用 10 个负边，并且您找到了一条从 A 到 B 的长度为 10 且不使用负边的路径，而另一条从 A 到 B 的长度为 5 的路径使用了三个负边缘；您还不知道哪一个会导致更好的解决方案（或根本没有解决方案），因为从 B 到 C 的路径中可能有 8 个负边。因此，在每个节点，您不仅需要记录一对 (path length, # of negative edges)，你需要记录一组所有最好的这样的对。
希望这能让您了解如何调整 Dijkstra 算法来解决您的问题；还有一些细节需要您自己填写。