幅優先探索の第一引数に渡すgraphを辞書から作成する

元データ

# 元データ
data = [
    {'node1': 1000, 'node2': 1050, 'direction': 0},
    {'node1': 1100, 'node2': 1000, 'direction': 1},
    {'node1': 1150, 'node2': 1200, 'direction': 2}
]

directionの値の意味

directionの値	意味
0	無方向
1	一方通行
2	双方向

元データからgraph作成

# 元データからgraph作成
def build_graph(data):
    graph = {}

    for edge in data:
        n1, n2, d = edge['node1'], edge['node2'], edge['direction']

        if d == 1:  # 片方向
            graph.setdefault(n1, []).append(n2)
            graph.setdefault(n2, [])  # 孤立ノードも確保しておく
        elif d == 2:  # 両方向
            graph.setdefault(n1, []).append(n2)
            graph.setdefault(n2, []).append(n1)
        # 無方向 (d == 0) は無視

    return graph

graph = build_graph(data)

作成されたgraph出力

from pprint import pprint
pprint(graph, width=1)

pprintは、見やすく出力するためのツール。データ数が少なく改行されなかったので、width引数を追加した。

{1000: [],
 1100: [1000],
 1150: [1200],
 1200: [1150]}

作成されたgraphのイメージ

スタートとゴールの設定

start_node = '1000'
goal_node = '1200'

最短経路探索

使用する関数については以下参照。

幅優先探索で最短経路を求める

数値ではなく文字列であることによるKeyError。

原因は定義部分で文字列にしていたから。

start_node = '1000'
goal_node = '1200'

数値に修正する。

start_node = 1000
goal_node = 1200

エラーは解消、最短経路はNone。

{1000: [],
 1100: [1000],
 1150: [1200],
 1200: [1150]}
最短経路: None

最短経路を出すために、元データを修正する。

# 元データ
data = [
    {'node1': 1000, 'node2': 1050, 'direction': 1},
    {'node1': 1050, 'node2': 1200, 'direction': 2},
    {'node1': 1200, 'node2': 1250, 'direction': 1},
    {'node1': 1250, 'node2': 1300, 'direction': 1},
    {'node1': 1100, 'node2': 1000, 'direction': 1},
    {'node1': 1100, 'node2': 1250, 'direction': 1},
]

{1000: [1050],
 1050: [1200],
 1100: [1000, 1250],
 1200: [1050, 1250],
 1250: [1300],
 1300: []}

start_node = 1000
goal_node = 1200

最短経路: [1000, 1050, 1200]