今日解いた問題3

今日というか今日と昨日

単一始点最短経路問題(ベルマンフォード)

ある頂点sからのすべての頂点の最短経路 d[j] > d[i] + costこの条件を１度使っただけでは明らかに最短にならないので 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
２番めの最短経路をだす問題
priority_queueがなかったのでかなり汚い感じになった
基本方針はすべての頂点に対して２番めの最短経路も持っとくこと

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