C++ ダイクストラ法

https://blog.logicky.com/2017/02/01/python3-%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%EF%BC%88%E9%87%8D%E3%81%BF%E4%BB%98%E3%81%8D%E3%82%B0%E3%83%A9%E3%83%95%E3%83%BB%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%8E%A2%E7%B4%A2/ — blog.logicky.com

上記はPythonでやっていました。C++でやってみます。

参考: 最短経路問題(ダイクストラ法)

対象のグラフ

f:id:edo1z:20200308070547p:plain

コード

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
const int INF = 1e9;

int n = 8; // 頂点の数

int dijkstra(Graph &G, int start, int goal) {
  vector<int> costs(n, INF);
  vector<bool> visited(n, false);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;

  int now = start;
  costs[now] = 0;
  visited[now] = true;

  while(1) {
    for (int i = 0; i < G[now].size(); ++i) {
      if (!visited[i] && G[now][i] > 0) {
        if (costs[i] > G[now][i] + costs[now]) {
          costs[i] = G[now][i] + costs[now];
        }
        que.push(make_pair(costs[i], i));
      }
    }
    if (que.empty()) break;
    now = que.top().second;
    que.pop();
    visited[now] = true;
  }
  return costs[goal];
}

int main() {
  Graph G = {
    {0, 10, 0, 20, 0, 0, 0, 30},  // A (0)
    {10, 0, 10, 0, 0, 0, 0, 0},   // B (1)
    {0, 10, 0, 0, 20, 0, 0, 0},   // C (2)
    {20, 0, 0, 0, 0, 20, 0, 0},   // D (3)
    {0, 0, 20, 0, 0, 0, 0, 20},   // E (4)
    {0, 0, 0, 20, 0, 0, 10, 0},   // F (5)
    {0, 0, 0, 0, 0, 10, 0, 10},   // G (6)
    {30, 0, 0, 0,20, 0, 10, 0}    // H (7)
  };
  int start = 5; // F
  int goal = 1; // B
  cout << dijkstra(G, start, goal) << endl;
}

priority_queueは、未訪問で最小コストの頂点が取得できる優先順位付きキューです。
Pairの左にコスト、右にグラフGのindexを入れます。
左の値（コスト）が小さい順に優先順位が高くなります。

対象のグラフ

コード

結果