我想知道是否有一种算法能够找到从起始节点到终止节点的最短节点序列。图表从起始节点分支出来,具有任意复杂性,并在终止节点处汇聚。所有节点之间的连接都没有权重。
我正在考虑采取从头部和尾部节点开始的探索步骤,直到两端的节点接触等,但我想知道是否存在“更好的方法”,以免重复发明轮子。
我正在考虑采取从头部和尾部节点开始的探索步骤,直到两端的节点接触等,但我想知道是否存在“更好的方法”,以免重复发明轮子。
使用广度优先搜索,时间复杂度为O(E+V)。这是在无权图上运行最快的算法。
这是计算机科学中一个非常经典的问题。根据您对图形的描述,您应该首先查看Dijkstra算法
BFS是解决这些问题的最佳方法,即使您想找到单个节点的最短路径,也必须遍历整个图形以查找是否存在其他可能的路径,而不仅仅是已获得的最短路径。
您还可以绘制BFS树,它将告诉您源节点和任何(也是单个)节点之间的确切最短路线。