重み付き有向グラフの全2点間の距離を求める Warshall–Floyd 法を python で書いてみる

アルゴリズム python グラフ

ワーシャル＝フロイド法とは

今回は有向グラフの情報が与えられたとき, 全ての始点から全ての終点までの最短距離をワーシャル＝フロイド(Warshall–Floyd)法と呼ばれるアルゴリズムで求めていきます. 有向グラフの最短距離を求めるアルゴリズムのうち, ベルマン＝フォード法は以前紹介しました:
wakabame.hatenablog.com

今回紹介するワーシャル＝フロイド法では, 頂点の集合を V としたとき, 任意の頂点 i,j に対してその間の最短距離を一挙に計算してしまいます. その代わり, 計算量は O(|V|^3) とやや大量になってしまいます.

続きを読む

典型的な DP (動的計画法) のパターンが整理されていたので Python で書いてみる

アルゴリズム python 動的計画法DP

動的計画法(DP)について, qiita でまとめられました

qiita.com
勉強になったのでメモ代わりに. やはり数列の添え字は0から始めて記述したほうが実装との親和性が高そうなので, 以下では数列は a[0], a[1],\cdots ,a[N-1] として書きます. ここで, N は数列の要素数を表します.

1. 最大和問題

N要素を持つ数列 a[0], a[1],\cdots ,a[N-1] から任意の個数の項を選んで和を取った時の最大値

def max_sum(N, a):
    dp = [0] * (N + 1)
    for i in range(N):
        dp[i + 1] = max(dp[i], dp[i] + a[i])
    return dp[N]
続きを読む

有向グラフ上の2点間の最短距離を求めるアルゴリズム Bellman–Ford 法を python で書いてみる

python アルゴリズム グラフ

有向グラフとは

有向グラフ(directed graph)とは, 頂点(vertex)と辺(edge)からなり, 辺は (v_1, v_2, c) の形式を持ち, 頂点 v_1 から頂点 v_2 へはコスト c で移動できることを表しています. 辺に対して逆向きの進路があるとは限らず, あったとしても同じコストとは限りません.
今回はグラフの情報と始点が与えられたとき, 各頂点への最短距離をベルマン＝フォード法と呼ばれるアルゴリズムで求めていきます.
また, 有向グラフ上の2点間の最短距離を求めるアルゴリズムにはダイクストラ(Dijkstra)法と呼ばれるものもありますが, ベルマン＝フォード法の強みは辺の重みは負でもよいことが挙げられます.
一方, 負の重みを持つ辺があるときに考えなくてはならないのは負閉路の検出です. 閉路を一周するごとに距離をマイナスにすることができるものが存在する場合, その閉路を何度も通ることで最短距離をいくらでも縮めることができてしまい, 最短経路が定まりません. ですので負閉路が存在(かつ始点から到達)する場合には最短距離の代わりに警告を返します.

続きを読む

ABC070 の D 問題を python で解いてみる

ABC-D python 競技プログラミング AtCoder グラフ

木構造の距離を求める問題演習として, AtCoder Beginner Contest 070 の D 問題の解説をしてみます.

問題はこちら
abc070.contest.atcoder.jp

続きを読む

重み付き木構造上の2点間の距離を求めるアルゴリズムを python で書いてみる

python アルゴリズム グラフ

グラフの一種である木構造での距離を求めるアルゴリズムを考えます.

グラフとは

詳しくは グラフ理論 - Wikipedia などの記述をご参照ください.
グラフ(graph)とは頂点(vertex)と辺(edge)からなる構造を表しており, 頂点同士が辺によって繋がっていることを表しているものです（頂点の集合は自然数の部分集合と同型なので, それぞれの頂点には何番目の頂点かを表す自然数が割り当てられます. 一般には辺それぞれには実数の重みがあり, その頂点同士の移動にかかるコストを表しています. 辺は (v_1, v_2, c) の形式を持ち, 頂点 v_1 から頂点 v_2 はコスト c で隣接していることを表しています. 重み付きでない場合は, c=1 と理解します.
辺に向きがあるもの（つまり, 2つの頂点について行けるのに戻れなかったりコストが等しくなかったりするもの）を有向グラフ(directed graph), 辺に向きがないもの（つまり, 頂点間のコストは行きと帰りで等しいもの）を無向グラフ(undirected graph)といいます. 無向グラフでは (v_1, v_2, c) なる辺があったとき, 逆向きの (v_2, v_1, c) を辺にもつ有向グラフと解釈することもできます.

続きを読む

AGC019 の C 問題を python で解いてみる。

python 競技プログラミング AtCoder AGC-C

本記事では先日開催された AtCoder Grand Contest 019 の C 問題の解説を試みます.
ちなみに私は本番中には解けず, 解説や他の人のコードを参考にさせていただきました.

問題はこちら
agc019.contest.atcoder.jp


スタート地点からゴール地点までの最短ルートの長さを求める問題ですね. 例からはなんとなく,
1. 最短ルートはスタート地点とゴール地点を向かい合う角とする長方形の内側(と周辺)を通る
2. ゴールが北東にある場合は, 南, 西方向に進むことはない
3. なるべく噴水に沿って90度回転する
ということが読み取れそうです. また,
4. 直線ルートよりも遠くなってしまうにも関わらず噴水に沿って180度回転する場合もある
ということも言えそうです.
これらの検証はやらないことにして, コアになるコードを作っていきます.
詳しくロジックを理解したい方は,
https://atcoder.jp/img/agc019/editorial.pdf
を参考にしてください.

続きを読む

最長増加部分列の長さ取得アルゴリズムLISをpythonで書いてみる

python アルゴリズム

最長増加部分列(Longest Increasing Subsequence )とは

数列 \{ a_i\}_{i=1}^n が与えられたとき, その部分列 \{ a_{\rho(i)}\}_{i=1}^{n'} であって
1\leqq i< j\leqq n' のとき a_{\rho(i)}< a_{\rho(j)} を満たすものを増加部分列と言います.
その中で最も長いものの長さを求めるアルゴリズムを以下に説明していきます.

続きを読む