graph - 在两个节点之间的图中跟踪路径

Question

如果我们知道或不知道它们之间的路径长度，如何跟踪给定图中两个节点之间的路径一次？（通过考虑邻接矩阵）

在邻接矩阵和广度优先搜索之间找到有效的路径？

能否请您给出算法步骤。

提前谢谢你，卡马拉。

Answer 1

实际上，答案将取决于您正在寻找什么样的路径。

如果您正在寻找最短路径，那么您可以尝试实现Dijkstra 算法，该算法运行速度也非常快。

如果你只是想找到一条路径，不管它有多长，那么BFS是一个很好的解决方案，因为它会在“最浅”的地方找到它，尽管它不能保证它是最短的。

您的其他选项是DFS，它将首先搜索最深的路径和Bellman-Ford，它也将给出最短路径，但在比 Dijkstra 更一般的情况下，它会更慢。

如果您想要所有可能的路径，则可以重新实现这些算法中的任何一个来执行图形的标记，从而获得所有可能的路径。