今日解いた問題3
今日というか今日と昨日
単一始点最短経路問題(ベルマンフォード)
ある頂点sからのすべての頂点の最短経路
d[j] > d[i] + cost
この条件を1度使っただけでは明らかに最短にならないので
update
変更がなくなるまでループを繰り返す
INF = 100_000 G = [[INF, 2, 5, INF, INF, INF, INF], [2, INF, 4, 6, 10, INF, INF], [5, 4, INF, 2, INF, INF, INF], [INF, 6, 2, INF, INF, 1, INF], [INF, 10, INF, INF, INF, 3, 5], [INF, INF, INF, 1, 3, INF, 9], [INF, INF, INF, INF, 5, 9, INF]] def shotest_path(s) d = Array.new(G.size, INF) d[s] = 0 loop do update = false G.each_with_index do |row, i| row.each_with_index do |cost, j| next if cost == INF || d[i] == INF if d[j] > d[i] + cost d[j] = d[i] + cost update = true end end end break unless update end d end p shotest_path(0) # => [0, 2, 5, 7, 11, 8, 16]
単一始点最短経路問題(ダイクストラ)
ベルマンフォードと目的は一緒
まだ訪れていない頂点の中から最短の頂点を見つけてそこから他の頂点への経路のコストを得る
INF = 100_000 G = [[INF, 2, 5, INF, INF, INF, INF], [2, INF, 4, 6, 10, INF, INF], [5, 4, INF, 2, INF, INF, INF], [INF, 6, 2, INF, INF, 1, INF], [INF, 10, INF, INF, INF, 3, 5], [INF, INF, INF, 1, 3, INF, 9], [INF, INF, INF, INF, 5, 9, INF]] def dijkstra(s) size = G.size d = Array.new(size, INF) used = Array.new(size, false) d[s] = 0 loop do min_node = -1 size.times do |i| min_node = i if !used[i] && (min_node == -1 || d[min_node] > d[i]) end break if min_node == -1 used[min_node] = true size.times do |i| d[i] = [d[min_node] + G[min_node][i], d[i]].min end end d end p dijkstra(0) # => [0, 2, 5, 7, 11, 8, 16]
全点対最短経路( ワーシャルフロイド)
すべての頂点からそれ以外のすべての頂点の最短経路
i
からj
までのパスの中で頂点k
通るか通らないかのDP
通るときはg[i][k] + g[k][j]
で通らない時はg[i][j]
ホントはd[k][i][j]
とかなるんだけどループ内で省略してる
INF = 100_000 def warshall_floyd g = [[0, 2, 5, INF, INF, INF, INF], [2, 0, 4, 6, 10, INF, INF], [5, 4, 0, 2, INF, INF, INF], [INF, 6, 2, 0, INF, 1, INF], [INF, 10, INF, 0, INF, 3, 5], [INF, INF, INF, 1, 3, 0, 9], [INF, INF, INF, INF, 5, 9, 0]] size = g.size size.times do |k| size.times do |i| size.times do |j| g[i][j] = [g[i][j], g[i][k] + g[k][j]].min end end end g end p warshall_floyd # [[0, 2, 5, 7, 11, 8, 16], [2, 0, 4, 6, 10, 7, 15], [5, 4, 0, 2, 6, 3, 11], [7, 6, 2, 0, 4, 1, 9], [7, 6, 2, 0, 4, 1, 5], [8, 7, 3, 1, 3, 0, 8], [12, 11, 7, 5, 5, 6, 0]]
アリ本のP102
2番めの最短経路をだす問題
priority_queueがなかったのでかなり汚い感じになった
基本方針はすべての頂点に対して2番めの最短経路も持っとくこと
N = 4 M = 4 INF = 100_000 G = [[INF, 100, INF, INF], [100, INF, 250, 200], [INF, 250, INF, 100], [INF, 200, 100, INF]] def solve d1 = Array.new(N, INF) used1 = Array.new(N, false) d2 = Array.new(N, INF) used2 = Array.new(N, false) d1[0] = 0 d2[0] = 0 loop do v = [-1, 1] N.times do |i| v = [i, 1] if !used1[i] && (v[0] == -1 || d1[v[0]] > d1[i]) v = [i, 2] if !used2[i] && (v[0] == -1 || d2[v[0]] > d2[i]) end break if v[0] == -1 eval("used#{v[1]}[#{v[0]}]=true") N.times do |i| d = eval("d#{v[1]}[#{v[0]}]") + G[v[0]][i] if d < d1[i] d, d1[i] = d[i], d end if d > d1[i] && d < d2[i] d2[i] = d end end end d2[N-1] end p solve # => 450