1

有向グラフを表す辞書があります。例えば...

myDict = {'foo': ['hello', 'stack'], 'bar' : ['over', 'flow']}

これは、'foo'ノードが'hello'と'stack'を指し、'bar'ノードが'over'と'flow'を指すことを意味します。

また、任意の 2 つのノード間の最短パスを見つけるために幅優先検索を実行するためのコードも作成しました...

from collections import deque

def breadthFirstSearch(graph, start, end):
    q = deque()
    path = (start, )
    q.append(path)
    visited = set([start])
    while q:
        path = q.popleft()
        last_node = path[-1]
        if last_node == end:
            return path
        for node in graph[last_node]:
            if node not in visited:
                visited.add(node)
                q.append(path + (node,))
    print 'There is no path from ' + start + ' to ' + end + '.'
    return None

私の質問は次のとおりです。この幅優先検索を変更して、最大の最短パスとそのパスの開始ノードと終了ノードが得られるようにすることは可能ですか?

4

1 に答える 1

1

あなたの問題は「グラフ直径問題」と呼ばれます。

幅優先検索は、幅優先検索ツリーを作成します。一般に、2 つのノード間の最長のツリー パスは、非ツリー エッジが存在するため、2 つのノード間の最長パスよりも長くなります。いいえ、BFS に直接それをさせることはできません。

BFS はツリーの場合はうまくいきますが、やや重要です。

グラフのいくつかの制限されたクラスの直径を見つけることができる「辞書式幅優先検索」と呼ばれるバリアントがあります。LBFS が動作する場所で遭遇したグラフ クラスは、ツリーのように見える傾向がありました。

編集：もちろん、各ノードから開始してBFSを1回実行し、BFSが報告する最長のパスを把握できます。または、非常に洗練されたFloyd-Warshall アルゴリズムを使用することもできます。

于 2013-05-26T02:03:16.690 に答える