我想知道是否存在一种算法,通过从头节点到尾节点的图形来查找最短的节点序列 . 该图从头节点分支出来并且是任意复杂的并且收敛于尾节点 . 节点之间的所有连接都是未加权的 .
我正在考虑解决这个问题,从头部和尾部节点采取探索性步骤,直到图形任何一端的节点触摸等,但我想知道在我(重新)发明一个之前是否存在“更好的轮子” .
使用breadth first search,它在O(E V)中运行 . 它会在未加权的图表上显示出来 .
这是计算机科学中最美丽的问题之一 . 鉴于您对图表的描述,您应首先查看Dijkstra's algorithm
对于这些类型的问题,BFS是最好的,即使您想找出单个节点最短路径,您已经遍历整个图形以查找是否除了已经获得的最短路径之外还有其他可能的路径 .
您还可以绘制一个BFS树,它将告诉您源和任何(也是单个)节点之间的最短路径 .
3 回答
使用breadth first search,它在O(E V)中运行 . 它会在未加权的图表上显示出来 .
这是计算机科学中最美丽的问题之一 . 鉴于您对图表的描述,您应首先查看Dijkstra's algorithm
对于这些类型的问题,BFS是最好的,即使您想找出单个节点最短路径,您已经遍历整个图形以查找是否除了已经获得的最短路径之外还有其他可能的路径 .
您还可以绘制一个BFS树,它将告诉您源和任何(也是单个)节点之间的最短路径 .