蟻本 p102 Roadblocks(ダイクストラ)

蟻本のプログラムを写経しながら、分かりにくかったところをコードにコメントしたのでそのメモ。
辺の表現や変数名なども自分の分かりやすいものに変えてある。

ダイクストラの気持ち

「最短距離を一つずつ確定させていくアルゴリズム」になっている。負の重みが無ければ, 最短距離が確定した頂点から到達できる頂点で最も距離が短い頂点を最短距離として確定していける. うーん, 文章にするとやっぱり小難しい、、

以下の記事あたりが図が載ってて理解しやすいので, 手書きで書いてみると理解しやすい

ダイクストラの実行手順は以下.

スタート地点を最短距離0とする. その他の点は∞にする.
最短距離未確定の頂点から, 最短距離が最も小さい頂点 v を取り出す
v を最短距離確定済みにする
v から到達できる頂点に対して, 最短距離を更新（= 辺をすべて調べている）
2〜5までを全ての頂点への最短距離が確定するまでくり返す

上記2の「最短距離が最も小さい点の探索」のやり方で計算量が変わる. 愚直実装ならO(|v|×|v|)となり、優先度付きキューならO(|E|×log |v|)となる.（|v|は頂点数, |E|は辺数）

というわけで, 問題を見ていく

問題（超ざっくり）

N個の頂点1〜NとM個の辺からなる無向グラフがあります。
頂点1から頂点Nに移動する経路で2番目に短いものを出力せよ。

入力方式

N M
ai bi costi
.
.
.
am bm costm

入力例

4 4
1 2 100
2 4 200
2 3 250
3 4 100

答え

450
（最短経路は300）

まずは最短経路を考える

まずは最短経路を求められるダイクストラのコード。これに手を加えて、2番目に短い経路を求められるようにする

#include <bits/stdc++.h>
using namespace std;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
using pint = pair<int, int>;
struct Edge {
  // 頂点, 重み
  int to, cost;
  Edge(int t, int c) : to(t), cost(c) {}
};
using Graph = vector<vector<Edge>>;

// ダイクストラ
// 頂点start から グラフg上の各頂点への最短距離をdに格納する
void dks(int start, Graph &g, int d[]) {
  // スタート地点（頂点0）までの距離は0として初期化
  d[start] = 0;

  // スタート地点からの距離が確定していない点をpairで保持
  priority_queue<pint, vector<pint>, greater<pint>> que;
  que.push(pint(start, 0));  // スタート地点を初期値とする

  // スタート地点からの距離が確定していない点について,
  // 距離が最も短い点から順番に距離を確定
  while (!que.empty()) {
    // 現在の点
    pint cur = que.top();
    que.pop();

    int v = cur.second;     // 頂点
    int d_min = cur.first;  // 最短距離

    // 既に、より短い経路を発見済み
    if (d[v] < d_min) {
      continue;
    }

    // 現在の点から到達できる点について、最短距離を更新できるか調べる
    for (auto next : g[v]) {
      if (d[next.to] > d[v] + next.cost) {
        d[next.to] = d[v] + next.cost;
        que.push(make_pair(d[next.to], next.to));
      }
    }
  }
}

int main() {
  int n, m;
  cin >> n >> m;

  Graph g(n);  // 無向グラフ
  int d[n];    // スタート地点から, 各頂点までの最短距離

  // 最短距離をINFで初期化
  for (int i = 0; i < m; i++) {
    d[i] = IINF;
  }

  // グラフを入力
  for (int i = 0; i < m; i++) {
    int a, b, cost;
    cin >> a >> b >> cost;
    a--, b--;
    g[a].push_back(Edge(b, cost));
    g[b].push_back(Edge(a, cost));
  }

  // スタート地点を0として、ダイクストラを適用
  dks(0, g, d);

  cout << d[n - 1] << endl;
}

次に2番目に短い経路を考える

基本は最短経路とほぼ同じ方針で「距離が確定した頂点からの2番目に短い経路を探索しながら確定していく」というのを実装する。

じゃあ2番目に短い経路ってどういう経路？

というところがポイントになるが、最短距離が確定した点をxとすると、2番目に短い経路は以下のどちらかとなる

xに隣接した頂点までの最短経路 + 隣接した頂点までのコスト
xに隣接した頂点までの2番目に短い経路 + 隣接した頂点までのコスト

ここが理解するのに少し躓いたところなので、図にしてみるとこんな感じ。（汚くてごめんなさい）

f:id:nakashiii:20211217212028j:plain

コードは以下。最短経路のコードから変更したところにコメントを記載してある。

#include <bits/stdc++.h>
using namespace std;
const int IINF = 0x3f3f3f3f;
using pint = pair<int, int>;
struct Edge {
  int to, cost;
  Edge(int t, int c) : to(t), cost(c) {}
};
using Graph = vector<vector<Edge>>;

// 2番目に短い経路をd2に保存
void dks(int start, Graph &g, int d[], int d2[]) {
  d[start] = 0;

  priority_queue<pint, vector<pint>, greater<pint>> que;
  que.push(make_pair(start, 0));

  // 2番目に短い経路は以下のどちらか。両方とも優先キューに追加しながら探索
  // - 隣接した頂点までの最短経路 + 隣接した頂点までのコスト
  // - 隣接した頂点までの2番目に短い経路 + 隣接した頂点までのコスト
  while (!que.empty()) {
    pint cur = que.top();
    que.pop();

    int v = cur.second;     // 頂点
    int d_min = cur.first;  // 最短距離

    // 既に、最短経路、２番目に短い経路を発見済み
    if (d2[v] < d_min) {
      continue;
    }

    // 隣接頂点の最短経路と2番目に短い経路を更新する
    for (auto next : g[v]) {
      int d2_min = d_min + next.cost;  // 2番目に短い経路(仮)を計算

      // 2番目に短い経路(仮)が, 最短距離だった場合
      if (d[next.to] > d2_min) {
        swap(d[next.to], d2_min);
        que.push(make_pair(d[next.to], next.to));
      }

      // 2番目に短いことが確定した場合
      if (d2[next.to] > d2_min && d[next.to] < d2_min) {
        d2[next.to] = d2_min;
        que.push(make_pair(d2[next.to], next.to));
      }
    }
  }
}

int main() {
  int n, m;
  cin >> n >> m;

  Graph g(n);
  int d[n];
  int d2[n];  // 二番目に短い経路

  for (int i = 0; i < m; i++) {
    d[i] = IINF;
    d2[i] = IINF;  // 二番目に短い経路
  }

  for (int i = 0; i < m; i++) {
    int a, b, cost;
    cin >> a >> b >> cost;
    a--, b--;
    g[a].push_back(Edge(b, cost));
    g[b].push_back(Edge(a, cost));
  }

  dks(0, g, d, d2);

  cout << d2[n - 1] << endl;
}

感想

ダイクストラの気持ちが少しだけ分かってよかった

nakashiiiの自由帳

自由に書きます