第5章
5.1 ダイクストラのアルゴリズム
ある1つの頂点から、各頂点に向かう最短経路を求めるアルゴリズム。
コストが非負の時のみに動作することに注意。頂点の数をN、辺の数をEとして、O(N**2)とO((N+E)logN)の2つのやり方がある（正直N**2の方は競プロ向けではない）。前者は完全グラフ（頂点の数Nに対し、辺の数がN**2）のような「密なグラフ」に有効。後者は、例えばE=N**2の時O(N**2logN)になり、辺の数が多いと前者よりも時間がかかってしまうデメリットがあるため、「疎なグラフ」（頂点と辺の数がほぼ同じ。この場合O(NlogN)程度になり、O(N**2)より計算量が小さい。）に有効。
O(N**2)の方はわかりやすい実装。全ての頂点について、それを経由して目的の頂点まで行くことがコストの節約につながるかを判定する。頂点を選ぶのにO(N)、それを経由して経路が短くなるかの判定を残りの頂点について確認するのにO(N)（これは内側のループ）なので、O(N**2)かかる。
用意するべきは、頂点i,j間の距離が入った二次元配列cost[i][j]、それに加えて、その頂点を途中で通過するかどうかを判断したか否かを持っておく真理テーブル、そして、最短経路が入るコストテーブルC[i]。
まず、出発点から直接行ける頂点についてコストテーブルを更新し、真理値表のスタートのところを通過済みにしておく。それから、まだ途中の経路として検討していない頂点の中で、コスト最小なものを取り上げ、それを経由した方が果たして距離が短くなるかを、すべての点について走査していく。これを、全ての頂点が途中に通過するかどうかを判定し終えるまで続ける。
O((N+E)logN)の場合もだいたいO(N**2)の時と同じ考え方で、全ての頂点が途中に通る点として考慮されるまでループを回す、というやり方をとる。ただ、頂点の管理にヒープを使うという違いがある。
用意するべきは、i番目の要素に頂点iからjに向かう経路のコストdが入ったリスト[d,j]を、N個の頂点全てについて集めたリストe。それに加えて、その頂点を途中で通過するかどうかを判断したか否かを持っておく真理テーブル、そして、最短経路が入るコストテーブルC[i]、さらに、[頂点Vまでの最短距離,Vの名前]というリストが入ったヒープが必要になる。
まずヒープの最小要素（つまり、最短距離d[V]が最も短いVのリスト[d[V],V]）を取り出し、頂点Vが経路として考慮済みであれば（真理値表を見て検討）それを捨てる。そうでなければ、Vを経路として考慮済みにし、e[V]の要素の中で、Vから次に向かう頂点e[1]が経路として未検討であれば、[e[0]+d[v],e[1]]をヒープに加えてe[1]を通過点として検討する候補に入れておく。このヒープが空になるまで操作が続く。
教科書にはコストの更新のところにif文が使われているが、これは取り出して経路として検討済みになった頂点と繋がる頂点に対して比較を行っている。距離で頂点をソートするとかいう不自然なことをしているからこんな風になっているのだが、実際はもっと単純に上記の実装をして、頂点として考慮したところだけ最短距離を更新していけばいい。（計算量自体は変わらないのだが、教科書の方が実装が圧倒的に面倒くさくてなんでこんなのを載せたのかわからない。あと流石にヒープはライブラリ使ってもいいよね......）
練習用問題
D: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder
提出したコード（O(N**2)の方。N=10**2くらいのケースではACもらってますが、流石にN=10**5ではTLEします。32,43行目の不等号にイコールがつくことに注意。あと37,48行目のコストが逆になっていることに注意（一方通行であるため）。）
Submission #8640764 - AtCoder Beginner Contest 035 | AtCoder
提出したコード（O((N+E)logN)の方。こっちは上手に書けばN=10**5でもACがもらえる。ポイントはちゃんとダイクストラのマクロを組むことと、頂点の最短経路更新を一回にすること。）
Submission #8641310 - AtCoder Beginner Contest 035 | AtCoder
5.2 フロイドのアルゴリズム
ワーシャルフロイド。計算量はNの3重ループなのでO(N**3)。ある2頂点の距離を入れたリストを、残りの点を経由して通過した際に距離が節約できるかを確かめてまわるアルゴリズム。ダイクストラが1対Nの関係を求めるものだったのに対し、こちらはN対Nの全ての頂点間の最短距離が求められる。
練習用問題・提出したコード（Python3だとTLEするのでPypyで）。双方向に連結されているので、最初にcostのリストに国iと国jを結ぶ距離cを代入する際、L[i][j] = L[j][i] = cとするように。
D - joisino's travel
Submission #8640345 - AtCoder Beginner Contest 073
練習問題↓（普通のワーシャルフロイドをやるだけじゃなくて、頂点iからiへの移動コストをちゃんと0に初期化すること、そしてそれが負になったら負の閉路が存在することを判定する。cost[i][i] < 0だけで閉路判定できるの楽だね！）
Aizu Online Judge
v,e = map(int,input().split())
cost = []
for i in range(v):
T = [float('inf')]*v
T[i] = 0
cost.append(T)
for i in range(e):
a,b,c = map(int,input().split())
cost[a][b] = c
for k in range(v):
for i in range(v):
for j in range(v):
cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])
flag = True
for i in range(v):
for j in range(v):
if cost[i][j] == float('inf'):
cost[i][j] = 'INF'
elif i == j and cost[i][j] < 0:
flag = False
break
if flag:
for i in range(v):
print(' '.join(map(str,cost[i])))
else:
print('NEGATIVE CYCLE')
5.3 有向グラフの探索（トポロジカルソート）
閉路のない有向グラフを、順序関係でとらえなおしたものをトポロジカルソートと呼ぶ。（その順番は一意に定まるわけではない。）
受け売りの説明だが、「例えばある講義A,B,C,D,Eをとるときに、BはAとEを履修していなければならず、AとDはCを履修していなければならず、EはDを履修していなければならないとした時に、どういう順序で講義を履修すればいいか？という関係を考えたもの（ここではC→A→D→E→B）」ということらしい。
まず、それぞれの頂点に入る矢印の本数をカウントするリストins[i]、それから頂点iから向かう矢印の行き先を入れたリストouts[i]を用意する。標準入力でグラフを受け取ると、まずはins[i]==0となる頂点、すなわち入る辺が存在しない頂点から探索を始める。木でとらえ直せば、これが木の根っこということになる。
入る辺が無い頂点を「入次数0の頂点」と呼ぶ。入次数0の頂点はキューに入る。このキューをQと表すと、Q.popleft()で先頭を取り出し、最終的な答えを入れるリストに入れる。この先頭要素から出る辺の行き先に対して、ins[i]をそれぞれ-1する。ins[i]が0になったら、それは入次数が0になったということなので、Qに入れる。これを順次繰り返し、木の根っこの方から（つまりトポロジカルソートの前の方から）調べていき、Qが空になるまでそれを続ける。
練習問題↓
Aizu Online Judge
from collections import deque
v,e = map(int,input().split())
ins = [0]*v
outs = [[] for i in range(v)]
ans = []
for i in range(e):
a,b = map(int,input().split())
outs[a].append(b)
ins[b] += 1
S = deque([])
for i in range(v):
if ins[i] == 0:
S.append(i)
while len(S) > 0:
cur = S.popleft()
ans.append(cur)
for e in outs[cur]:
ins[e] -= 1
if ins[e] == 0:
S.append(e)
for i in range(v):
print(ans[i])
練習問題↓
D - Restore the Tree
答え↓
Submission #8678690 - NIKKEI Programming Contest 2019
参考ページ↓
トポロジカルソートがわからなかったので調べてBFSで実装したのち、AtCoderの問題を解いてみた。 - Qiita
※実は、有向グラフが閉路を持たないことと、トポロジカルソート可能（トポロジカルソートした時に、要素数が元のDAGの要素数と一致する）であることは必要十分条件になっている。
有向グラフの閉路検査の問題↓（トポロジカルソート可能かだけを判定すればよい）
Aizu Online Judge
第6章
6.1 最小木
プリムのアルゴリズム
ほとんどダイクストラと構築が同じ。最小全域木（最短コストで木の各頂点を回れるようにしたもの）を構築するアルゴリズム。辺の長さをヒープで持っておいて、コストが小さい方から最小全域木を構成する辺として採用し、全部の頂点を見終わるまで続ける。
計算量は、素直な実装（n個の頂点を見て、その内側でn個の各頂点に対して、全域木までのコストを更新する）場合はO(N**2)だが、ヒープを使うことでO((N+E)logN)にすることができる。ただ、これもダイクストラと同じように、後者は密なグラフに弱い。
練習問題↓
Aizu Online Judge
import heapq
n = int(input())
ans = 0
cost = []
for i in range(n):
L = list(map(int,input().split()))
cost.append(L)
used = [False]*n
used[0] = True
edge = []
for i in range(n):
T = []
edge.append(T)
for i in range(n):
for j in range(n):
if L[i][j] != -1:
T[i].append([L[i][j],j])
P = T[0]
P.sort()
while len(P) != 0:
cur = heapq.heappop(P)
if cur[1] == True:
continue
cur[1] = True
cur[0] += ans
for e in T[cur[1]]:
heapq.heappush(P,[e[0],e[1]])
print(ans)
クラスカルのアルゴリズム
フロイドのアルゴリズムと並んで簡単なんじゃないか？（嘘かも）これもプリム法と同じく全域木を構築するアルゴリズム。
UF木と組み合わせると楽なのでそうやって使う。[頂点A,Bを結ぶ辺のコスト,頂点A,頂点B]を要素として持つリストをまずは辺のコストでソートし、辺の短い方から使っていく。もし頂点Aと頂点Bが同じ木に属していなければ、その辺を木の辺として用いる（頂点A,Bを結ぶ）。属していれば、辺を捨てる。これを全ての辺についてやればいい。よって計算量自体は「辺を全部見るO(E)」と「辺をソートするO(ElogE)」と「UF木を構築するO(？)」になるけど、UF木を構築するのはクソ早くできるので、今回は辺のソートのみが問題になり、計算量はO(ElogE)となる。
練習問題↓
D - Built?
答えのコード↓（各頂点をもう一回インデックスつけ直して10**5までで扱えるようにする。張る辺が隣接する頂点どうしのみ考慮すればいいことから、x,yそれぞれでソートして辺の距離を出し、最大で2*(10**5)本くらいの辺に対してクラスカルのアルゴリズムをやってあげればいい。（Pythonだと流石にギリギリね）
Submission #8666576 - AtCoder Beginner Contest 065
練習問題↓
Aizu Online Judge
