检查两个节点之间的单源最短路径是否唯一

Question

给定一个未加权且无向的图，如何检查是否存在唯一的或多个最短路径？

提前致谢。

Answer 1

你可以使用Breadth-first search（我称之为modBFS）算法的修改版本，return两个节点之间的最短路径，修改包括标记你访问的第一个节点（不包括起始节点）所以下次你调用算法时它不会被访问，然后你再次调用 modBFS 但这次 modBFS 先前标记的节点（那是你访问的第一个节点）将不会被访问所以如果有另一个节点之间的路径将被 returned（请注意它将再次被 returned 为最短路径），您可以简单地检查距离是否相同。然后你可以重复标记你访问的第二个节点，然后是第三个等等，但请记住保留你获得的第一条路径的副本，因为你需要它知道你必须标记哪个节点，如伪代码

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

如果 path[i].mark 为 1

，BFS 将只访问节点

检查两个节点之间的单源最短路径是否唯一

Check if the single source shortest path between two nodes is unique

algorithm

graph-theory

breadth-first-search