给定一个无权无向图,如何检查是否存在唯一的最短路径或多个最短路径?
提前谢谢。

最佳答案

您可以使用修改后的Breadth-first search(我将称之为modbfs)算法,该算法返回两个节点之间的最短路径,修改内容包括标记您访问的第一个节点(不包括起始节点),以便下次调用该算法时不会访问它,然后再次调用modBFS,但这次modBFS先前标记的节点(这是您访问的第一个节点)将不会被访问,因此如果节点之间有另一条路径将被返回(请注意,它将再次返回最短路径),您只需检查距离是否相同然后,您可以重复这个标记您看到的第二个节点,然后是第三个节点,依此类推,但请记住保留您获得的第一个路径的副本,因为您需要它知道您必须将哪个节点标记为伪代码

modBFS(start_node,end_node){
    path=BFS(start_node,end_node)
    for i=0 to path.length
        path[i].mark=0
        path1=BFS(start_node,end_node)
        if path1.lenght == path.lenght
            return true
        path[i].mark=1
    return false

只有当路径[i]标记为1时,BFS才会访问节点

关于algorithm - 检查两个节点之间的单个源最短路径是否唯一,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/51347507/

10-08 22:16
查看更多