给定一个无权无向图,如何检查是否存在唯一的最短路径或多个最短路径?
提前谢谢。
最佳答案
您可以使用修改后的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/