如果找到多个最短路径，则抛出错误
给定一个无向加权图、起点和终点。您需要找到到达该端点的最短路径，但如果找到多个最短路径，则会抛出错误。我们将如何处理错误部分？有没有办法检查是否存在到目标节点的多条最短路径？
我的想法是，当我们从dijkstra算法中的优先级队列中弹出时，如果此时该节点是目标节点，那么我们检查该优先级队列中是否存在同一目标节点的另一个元素。 在放松期间，我们可以在距离小于或等于时进行推送，而不是仅在距离小于时才推送到队列。但我对此并不确定。
编辑-它是一个加权无向图
Given an undirected weighted graph, a start, and an end point. You need to find the shortest path to that end point, but throw an error if multiple shortest paths are found. How would we do the error part? Is there a way to check if multiple shortest paths to a destination node exist?
My idea is that when we pop out of the priority queue in dijkstra's algorithm, at that time if the node is the destination node, then we check if in this priority queue, another element exists for the same destination node.
During the relaxation, instead of only pushing to the queue if the distance is less than, we can push if the distance is less than or equal to. But I am not sure about it.
EDIT - Its a weighted undirected graph
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
实现此目的的一种方法是创建最短路径 DAG。每当您以成本 C 松弛从节点 A 到节点 B 的某些边时（假设从源到每个节点的当前最短距离存储在数组 dist 中），如果 dist[A] + C 大于 dist[B] 则不执行任何操作，如果 dist[A] + C 等于 dist[B]，那么我们可以使用与以前不同的路线在最短路径中到达 B，因此我们将 A 添加到可以在其最短路径中到达 B 的节点列表中（让我们将此数组称为 pars），所以我们将A添加到B的pars中，最后如果dist[A] + C小于dist[B]，那么我们更新dist[B]并清除pars[B]中先前的值，并将A添加到pars[ B]。
如果所有边权重都严格大于 0，则得到的图保证是 DAG。然后您可以使用一些简单的动态规划方法来计算到达目标节点的路径数，按拓扑顺序处理节点，然后计算路径数每个节点的路径数是到达该节点的路径数（pars[node] 中的节点）的总和。
希望这是有用且清晰的。
One way to do this is by creating a shortest path DAG. Whenever you relax some edge from node A to node B with cost C (assuming the current shortest distance from source to each node is stored in array dist), if dist[A] + C is greater than dist[B] then do nothing, if dist[A] + C is equal to dist[B], then we can reach B in a shortest path using a different route than before, so we add A to the list of nodes that can reach B in its shortest path (let's call this array pars), so we add A to pars of B, and finally if dist[A] + C is less than dist[B], then we update dist[B] and clear the previous values from pars[B], and add A to pars[B].
The resulting graph is guaranteed to be a DAG if all edge weights are strictly greater than 0. Then you can count the number of paths to the destination node using some easy dynamic programming methods, process node in a topological order, then the number of paths of each node is the sum of number of paths of nodes that reach it (nodes in pars[node]).
Hopefully this was useful and clear.