No Caffeine, No Life

プログラミング(主にPython)

ダイクストラ法

ABC 073 D - joisino's travel:ダイクストラ法、ワーシャルフロイド法、組み合わせ(itertools)

問題: D: joisino's travel - AtCoder Beginner Contest 073 | AtCoder 解説: 訪れる町が個と少ない。そこで、全通りの順列を全探索。 各点から各点への最短距離はダイクストラ法で求める。負の距離が無いし。 と、コンテスト中は考えた。これでうまくいく…

AOJ ALDS_1_12_C:単一始点最短経路 ダイクストラ法 (Dijkstra Algorithm)

AOJ ALDS 1_12_Bでは、O(|V^{2}|)のアルゴリズムだったが、優先度付キューを用いることでより高速化できる。 問題: 最短経路 | アルゴリズムとデータ構造 | Aizu Online Judge ここでは、隣接リストと優先度付キュー(pythonでいうところのheapq)を用いる。…

AOJ ALDS1_12_B: 単一始点最短経路 ダイクストラ法 (Dijkstra Algorithm)

ダイクストラ法:グラフG = (V, E)における単一始点最短経路を求めるためのアルゴリズム 問題: 最短経路 ダイクストラ法 | アルゴリズムとデータ構造 | Aizu Online Judge 以下は、隣接行列を用いたO(|V^{2}|)の解答例: