上記はPythonでやっていました。C++でやってみます。
参考: 最短経路問題(ダイクストラ法)
対象のグラフ
コード
#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