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]

編集：ベータで尋ねられたように、トポロジカルソートは次のとおりです。

# 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

Because you cannot topologically sort a graph with cycles (therefore undirected graphs are also out of the question as you can't tell which node should come before another).

Edit: After reading the comments, I think that's actually what @Beta meant.

于 2013-09-02T02:12:50.583 に答える