0

我有用 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]
4

2 回答 2

3

因为您不能对带有循环的图进行拓扑排序（因此无向图也不可能，因为您无法判断哪个节点应该位于另一个节点之前）。

编辑：阅读评论后，我认为这实际上是@Beta 的意思。

于 2013-09-02T02:12:50.583 回答
0

当存在循环时，拓扑排序不能保证最短路径的正确排序。

例如，我们有一个图表：

A->C, A->B, B->C, C->B, B->D

说正确的最短路径是：

A->C->B->D

但是拓扑排序可以生成一个顺序：

A->B->C->D

虽然它会B在访问时更新到正确的顺序C，但B不会再次被访问，因此无法将正确的权重传播到D. （路径恰好是正确的。）

于 2015-06-03T17:18:40.283 回答