始める無料で始める

Shortest Path II

すでに、目的地のノードが neighbors に含まれているかをチェックするコードはできています。次は、目的地のノードが neighbors に含まれていない場合の処理を、同じ関数に書き足していきます。

記述が必要なのは else ブロック、つまり node2 が neighbors に「含まれていない」場合のコードだけです。

この演習はコースの一部です

Pythonで学ぶネットワーク分析入門

コースを見る

演習の手順

  • .add() メソッドを使って、現在のノード node を集合 visited_nodes に追加し、すでに訪れたノードを記録します。
  • まだ訪れていない現在のノード node の「neighbors」を queue に追加します。これには、queue の .extend() メソッドとリスト内包表記を使います。.extend() は与えられたリスト内のすべての要素を末尾に追加します。
    • リスト内包表記の 出力式 と 反復変数 はどちらも n、iterable は neighbors のイテレータで、条件は n が未訪問ノード（visited nodes）に「含まれていない」ことです。

実践的なインタラクティブ演習

このサンプルコードを完成させて、この演習に挑戦してみましょう。

def path_exists(G, node1, node2):
    """
    This function checks whether a path exists between two nodes (node1, node2) in graph G.
    """
    visited_nodes = set()
    queue = [node1]

    for node in queue:
        neighbors = G.neighbors(node)
        if node2 in neighbors:
            print('Path exists between nodes {0} and {1}'.format(node1, node2))
            return True

        else:
            # Add current node to visited nodes
            ____

            # Add neighbors of current node that have not yet been visited
            queue.extend([____ for ____ in ____ if ____ not in ____])
コードを編集して実行