01 BFS 可以用于在只有 2 个权重的图中找到最短路径吗？
Can 01 BFS be used to find shortest path in a graph with only 2 weights?
我已阅读 this 关于 0-1 BFS 的文章，我知道它适用于 0-1 权重。然而，在文章的最后，作者提出了3个问题，其中一个正是我的问题。他在评论中指出，如果权重是任意两个数字 x 和 y，则不起作用。
但是为什么呢？使用的逻辑仍然成立。假设0<=x<=y，对于任意节点u，我们只会添加可以放宽的邻居。此外，所有距离你 x 的邻居都将被添加到双端队列的前面，而那些距离你 x 的邻居将被添加到双端队列的后面。这样，双端队列仍然会根据与当前节点的距离进行排序。
In addition, all the neighbors that are x away from u will be added to the front of the deque and those that are y away will be added at the back of the deque. This way, the deque will still be sorted based on distance from the current node.
当 x > 0 时，双端队列不保证排序。
假设 x=3 和 y=5，我们有这张图，需要找到从 A 到 E 的最短路径：
A --3--> B --3--> C
| |
5 3
| |
v v
D --------3-----> E
我们从队列中的[A:0]开始（到A的距离为0）。
这个条目被取出来，我们追加D:5和prependB:3，所以我们有[B:3,D:5]
我们取出 B:3 并在前面加上 C:6，所以我们有 [C:6,D:5]。这破坏了排序顺序，因此算法处于错误的立足点。它现在将首先在节点 C 而不是节点 D 上扩展，因此我们找到路径长度为 9 的 E，而路径为 8.
只有当 x=0 时，您才能保证此方法将保持队列排序。
我已阅读 this 关于 0-1 BFS 的文章，我知道它适用于 0-1 权重。然而，在文章的最后，作者提出了3个问题，其中一个正是我的问题。他在评论中指出，如果权重是任意两个数字 x 和 y，则不起作用。
但是为什么呢？使用的逻辑仍然成立。假设0<=x<=y，对于任意节点u，我们只会添加可以放宽的邻居。此外，所有距离你 x 的邻居都将被添加到双端队列的前面，而那些距离你 x 的邻居将被添加到双端队列的后面。这样，双端队列仍然会根据与当前节点的距离进行排序。
In addition, all the neighbors that are x away from u will be added to the front of the deque and those that are y away will be added at the back of the deque. This way, the deque will still be sorted based on distance from the current node.
当 x > 0 时，双端队列不保证排序。
假设 x=3 和 y=5，我们有这张图，需要找到从 A 到 E 的最短路径：
A --3--> B --3--> C
| |
5 3
| |
v v
D --------3-----> E
我们从队列中的[A:0]开始（到A的距离为0）。
这个条目被取出来，我们追加D:5和prependB:3，所以我们有[B:3,D:5]
我们取出 B:3 并在前面加上 C:6，所以我们有 [C:6,D:5]。这破坏了排序顺序，因此算法处于错误的立足点。它现在将首先在节点 C 而不是节点 D 上扩展，因此我们找到路径长度为 9 的 E，而路径为 8.
只有当 x=0 时，您才能保证此方法将保持队列排序。