No Caffeine, No Life

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

グラフ理論

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

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

ABC 061 D:Score Attack ベルマンフォード法

問題: D: Score Attack - AtCoder Beginner Contest 061 | AtCoder 解説: ベルマンフォード法を使うために、辺のコストをすべて負とする。(答えは、得られた最小値 x -1 ) 閉路が検出されれば、それがinfの場合。普通のベルマンフォードの法と異なり、終…

AOJ GRL_1_B:単一始点最短経路(負の重みをもつ辺を含む) ベルマンフォード法

問題: 単一始点最短経路 負の重み | グラフ | Aizu Online Judge 解説: プログラミングの雑記 ベルマンフォード法 解答例:

ABC 061 B:Counting Roads 隣接行列

問題: B: Counting Roads - AtCoder Beginner Contest 061 | AtCoder 解答例: 必ずしも隣接行列を使わなくてもよいのだけれど。。。

AOJ GRL_1_C:全点対間最短経路 ワーシャルフロイド法 (Warshall-Floyd's Algorithm)

全点対間最短経路問題 (APSP: All Pairs Shortest Path)を解くアルゴリズムのひとつにワーシャルフロイド法がある。 特徴: Gに負の閉路がない限り、Gに負の重みをもつ辺が存在しても適用可。 Gに負の閉路があるかどうかの判定に使える。すなわち、ある頂点v…

Python 3 Tips:グラフ理論(隣接行列と隣接リストの表現)

標準入力から、隣接行列・隣接リストを作る例。 隣接行列: のとき もしくは、 隣接行列: のとき 隣接リスト: のとき 隣接リスト:のとき 隣接リスト: のとき 隣接リスト: のとき

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}|)の解答例: