我有用Python实现的基本线性最短路径算法。根据我遇到的各种站点,这只适用于有向无圈图,包括、和。然而,我不明白为什么会这样。
我甚至在有圈和无向边的图上测试了这个算法,它工作得很好。
那么问题是,为什么线性最短路径算法不适用于无向循环图?边问题,这个算法的名称是什么?。
作为参考,下面是我为算法编写的代码:
def shortestPath(start, end, graph):
# First, topologically sort the graph, to determine which order to traverse it in
sorted = toplogi
我知道这通常是广度优先的,但我们被要求两者都做,我已经做到了广度优先……
我觉得这是一个使用深度优先搜索的典型例子,所以我希望我能在这里得到一些帮助……我试图通过深度优先搜索找到迷宫中的最短路径,但到目前为止,我还不能确切地知道如何做到这一点。这是我到目前为止的代码:
void maze::findPathRecursive(graph &g, int position, int goal) {
if (position == goal) {
isPath = true; //returns true if there is a path to the goal