使用 dijkstra 从队列中弹出最短路径的节点
Popping a node of a shortest path from the queue using dijkstra
我有一个使用正确实施的 dijkstra 算法计算的最短路径。它从A经过B，C，D和E到达F。所以整个最短路径是[A，B，C，D，E，F]。
现在我想从 G 到 F。当从队列中弹出 C 时，我意识到它是到 F 的最短路径的一部分。这是否意味着我也知道从 G 到 F 的最短路径是[G, H, C, D, E, F]?
我认为不是，因为你必须考虑从 H 到 C 的距离。
如果距离 [H, C] 很大，比方说大于距离 [H, I, F] 怎么办？
没有。但是确实意味着从C到F的最短路径是[C,D,E, F].
如果有更短的路径，P 那么我们构造一条从 A 到 F [A,B,[P]] 的新路径，它本质上比我们原来的路径更短。这是一个矛盾，因为我们假设 [A,B,C,D,E,F] 是从 A 到 F 的最短路径。
这可以推广证明最短路径的子路径也是最短路径。在您的情况下，这意味着如果从 G 到 F 的最短路径包含 C，则该最短路径包含 [C, D, E, F] 作为子路径。因为你不知道 C 是否在你的最短路径中，如果你存储从 C 到 F 的最短路径的权重，这个定理只会帮助你减少计算次数。
我有一个使用正确实施的 dijkstra 算法计算的最短路径。它从A经过B，C，D和E到达F。所以整个最短路径是[A，B，C，D，E，F]。
现在我想从 G 到 F。当从队列中弹出 C 时，我意识到它是到 F 的最短路径的一部分。这是否意味着我也知道从 G 到 F 的最短路径是[G, H, C, D, E, F]?
我认为不是，因为你必须考虑从 H 到 C 的距离。 如果距离 [H, C] 很大，比方说大于距离 [H, I, F] 怎么办？
没有。但是确实意味着从C到F的最短路径是[C,D,E, F].
如果有更短的路径，P 那么我们构造一条从 A 到 F [A,B,[P]] 的新路径，它本质上比我们原来的路径更短。这是一个矛盾，因为我们假设 [A,B,C,D,E,F] 是从 A 到 F 的最短路径。
这可以推广证明最短路径的子路径也是最短路径。在您的情况下，这意味着如果从 G 到 F 的最短路径包含 C，则该最短路径包含 [C, D, E, F] 作为子路径。因为你不知道 C 是否在你的最短路径中，如果你存储从 C 到 F 的最短路径的权重，这个定理只会帮助你减少计算次数。