問題
次のような重み付き無向グラフが与えられます。
🔹頂点数は $N$、辺の数は $M$ です。
🔹$i$ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結び、長さは $ C_i $ です。
このグラフに対して最短経路長を求めて下さい。
出力形式として、各頂点への最短距離を頂点 $1$ から頂点 $N$ まで順番に出力して下さい。
移動できない頂点の場合は、$-1$ を出力してください
[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ 1 \leqq M \leqq min(100000,N(N-1))/2 $
🔹$ 1 \leqq A_i < B_i \leqq N $
🔹$ 1 \leqq C_i \leqq 10000 $
解き方・ソースコード
ダイクストラ法を使ってこの問題を解いていきます。
ソースコードの冒頭で、グラフの情報を設定しています。
ここでは、頂点数、辺の数、および各辺の情報をタプルとしてリストに格納しています。
次に、隣接リストを作成しています。
このようにしておくことで、後続の処理で各頂点からつながっている辺を効率的に参照できるようになります。
また、このコードではPythonの組み込みモジュールheapqを使って優先度付きキューを実装しています。
これにより、次に探索すべき頂点を常に距離の短い順に処理することができます。
ダイクストラ法の実装部分では、優先度付きキューから取り出した要素が確定済みの頂点(kakutei変数)である場合はスキップしています。
また、確定していない隣接頂点について、現在の距離よりも短い経路が存在する場合は、その距離を更新し、優先度付きキューに加えます。
この処理を、優先度付きキューが空になるまで繰り返します。
最後に、各頂点までの最短距離を出力しています。
頂点までの最短距離が存在しない場合は-1を出力するようにしています。
[Google Colaboratory]
1 | #-------- 入力例1 --------- |
[実行結果(入力例1)]
頂点 1 までの最短距離 0 頂点 2 までの最短距離 14 頂点 3 までの最短距離 76 頂点 4 までの最短距離 22 頂点 5 までの最短距離 19 頂点 6 までの最短距離 37
各頂点への最短距離を求めることができました。