edo1z blog

プログラミングなどに関するブログです

C++ ダイクストラ法

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を入れます。
  • 左の値(コスト)が小さい順に優先順位が高くなります。

結果

50