无权图/树中给定两个节点间的最短路径

Question

我正在寻找一种算法，可以使用邻接矩阵确定无权图中两个节点之间的最短路径。我知道Dijkstra和Bellman-Ford算法，但没有一个是专门用于确定给定两个节点之间的最短路径的。非常感谢您的帮助。

- Dorin Rusu

---

这个问题可能太一般性/理论化了，最好在cs.stackexchange.com上得到答案。请参见图形标签：http://cs.stackexchange.com/questions/tagged/graphs - Jacob Foshee

可能是使用Dijkstra算法在邻接矩阵中查找最短路径的重复问题。此外，这篇论文描述了如何使用矩阵乘法计算最短路径。 - Ted Hopp

出于好奇，您认为为什么Dijkstra算法和Bellman-Ford算法不能用于查找两个节点之间的最短路径？ - templatetypedef

我并不是说它们不能被使用，只是我找到的那些变体不符合我的要求。 - Dorin Rusu

Answer 1

一个简单的选择是从第一个节点开始运行广度优先搜索，直到找到第二个节点。如果您为每个节点存储父指针，则可以从第一个节点到第二个节点读取路径。此外，这在图的大小线性时间内运行。

希望能有所帮助！

- templatetypedef