アルゴリズム図鑑 ~ グラフ探索

1. Breadth First Search

2. Depth First Search

CodePenのURLが不正です

3. BellmanFord Algorithm

4. Dijkstra Algorithm

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

using pii = pair<int, int>;
const int INF = numeric_limits<int>::max();

vector<int> dijkstra(int start, const vector<vector<pii>>& graph, vector<int>&dist){
    int n = graph.size();
    dist.assign(n, INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while(!pq.empty()) {
        auto [d, u] = pq.top();pq.pop();

        if (d > dist[u]) continue;
        
        for (auto [v, w] : graph[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    int n = 5;
    vector<vector<pii>> graph(n);

    // グラフの辺 (from → to, cost)
    graph[0].push_back({1, 2});
    graph[0].push_back({2, 4});
    graph[1].push_back({2, 1});
    graph[1].push_back({3, 7});
    graph[2].push_back({3, 3});
    graph[3].push_back({4, 1});

    vector<int> dist;
    vector<int> result = dijkstra(0, graph, dist);

    for (int i = 0; i < result.size(); ++i) {
        if (result[i] == INF) {
            cout << "dist[" << i << "] = INF" << endl;
        } else {
            cout << "dist[" << i << "] = " << result[i] << endl;
        }
    }

    return 0;
}