Pythonのショートカットで2つの都市間の長さを調べるプログラム

n個の都市があり、都市が2種類の道路で接続されているとします。高速道路とショートカット。現在、地図があり、高速道路のみが地図上にあり、すべてのショートカットはありません。都市の輸送部門は、高速道路とショートカットを利用して都市を接続する輸送を開始したいと考えています。 2つの都市の間に高速道路がない場合、2つの都市の間に近道があることを私たちは知っています。ここでのタスクは、開始都市から他のすべての都市へのショートカットの観点から最小距離を見つけることです。

したがって、入力が次のような場合

開始頂点が1の場合、出力は312になります。

ショートカットのみを使用する場合、都市1と2の間のパスは1-> 3-> 4-> 2になり、コストは3になります。

同様に、

1と3：1-> 3、コスト1。

1と4：1-> 3-> 4、コスト2。

これを解決するには、次の手順に従います-

• グラフ：=nセットを含む新しいリスト
• エッジの各ペア（x、y）について、
  • x：=x-1
  • y：=y-1
  • グラフにyを挿入[x]
  • xをグラフに挿入[y]
• temp_arr：=値-1を含むサイズnの新しい配列
• b_set：=キーs-1を含む新しいマップ
• f：=0からnまでの数値とb_setのセットの差を含む新しいセット
• インデックス：=0
• b_setのサイズが0より大きい場合は、
  • b_setの各要素aについて、実行します
    • temp_arr [a]：=インデックス
  • nxt：=b_setのサブセットではないグラフの値を含む新しいマップ
  • f：=fとnxtの差を設定
  • b_set：=nxt
  • index：=index + 1
• temp_arrのゼロ以外の値を返す

例

理解を深めるために、次の実装を見てみましょう-

def solve(n, edges, s):
    graph = [set() for i in range(n)]
    for (x, y) in edges:
        x -= 1
        y -= 1
        graph[x].add(y)
        graph[y].add(x)
    temp_arr = [-1] * n
    b_set = {s - 1}
    f = set(range(n)).difference(b_set)
    index = 0
    while len(b_set) > 0:
        for a in b_set:
            temp_arr[a] = index
        nxt = {f for f in f if not b_set.issubset(graph[f])}
        f = f.difference(nxt)
        b_set = nxt
        index += 1
    return (' '.join(str(t) for t in temp_arr if t > 0))    

print(solve(4, [(1, 2), (2, 3), (1, 4)], 1))

入力

4, [(1, 2), (2, 3), (1, 4)], 1

出力

3 1 2