为什么线性最短路径算法对无向循环图不起作用？

Question

我已经用Python实现了基本的线性最短路径算法。根据我遇到的各种网站，这只适用于有向无环图，包括this,this和this。然而，我看不出为什么会这样。

def shortestPath(start, end, graph):
    # First, topologically sort the graph, to determine which order to traverse it in
    sorted = toplogicalSort(start, graph)

    # Get ready to store the current weight of each node's path, and their predecessor
    weights = [0] + [float('inf')] * (len(graph) - 1)
    predecessor = [0] * len(graph)

    # Next, relaxes all edges in the order of sorted nodes
    for node in sorted:
        for neighbour in graph[node]:

            # Checks if it would be cheaper to take this path, as opposed to the last path
            if weights[neighbour[0]] > weights[node] + neighbour[1]:

                # If it is, then adjust the weight and predecessor
                weights[neighbour[0]] = weights[node] + neighbour[1]
                predecessor[neighbour[0]] = node

    # Returns the shortest path to the end
    path = [end]
    while path[len(path) - 1] != start:
        path.append(predecessor[path[len(path) - 1]])
    return path[::-1]

编辑：正如Beta所要求的，下面是拓扑排序：

# Toplogically sorts the graph given, starting from the start point given.
def toplogicalSort(start, graph):
    # Runs a DFS on all nodes connected to the starting node in the graph
    def DFS(start):
        for node in graph[start]:
            if not node[0] in checked:
                checked[node[0]] = True
                DFS(node[0])
        finish.append(start)

    # Stores the finish point of all nodes in the graph, and a boolean stating if they have been checked
    finish, checked = [], {}
    DFS(start)

    # Reverses the order of the sort, to get a proper topology; then returns
    return finish[::-1]

Answer 1

因为您无法用圈对图进行拓扑排序（因此，无向图也是不可能的，因为您无法判断哪个节点应该在另一个节点之前）。

编辑：看了评论后，我想这就是@beta的意思。