dijkstra
(src/Graph/dijkstra.hpp)

• View this file on GitHub
• Last update: 2023-11-13 00:21:55+09:00
• Include: #include "src/Graph/dijkstra.hpp"

dijkstra

グラフの辺に負の重みが存在しない際に使える、ある頂点からの他の頂点への最短距離を計算します。

頂点数 $V$, 辺の数 $E$ とすると、 $O(ElogV)$ で計算できます。

dijkstra

dijkstra<T = long long>(int start, Graph<T> &G, T start_val = 0)

• $Graph$ の型 $T$ (指定しないと long long)
• 始点 $s$
• 始点の距離 start_val (指定しないと0) が必要です。

返り値はstd::vector<std::pair<T, int>> distです。 dist[v].first は $s$ から $v$　までの最短距離、 dist[v].second は $s$ から $v$　までのある最短距離のパスで $v$ の一つ前の頂点が入ります。

Depends on

• Graph (src/Graph/Graph.hpp)

Verified with

• test/Graph/dijkstra_Shortest_Path.test.cpp

Code

#pragma once

#include <cassert>
#include <limits>
#include <queue>
#include <vector>

#include "Graph.hpp"

namespace lib {
template <class T = long long>
std::vector<std::pair<T, int>> dijkstra(int start, const Graph<T>& G,
                                        T start_val = 0) {
    assert(0 <= start && start < (int)G.size());
    // 距離 と どこからかを保持
    std::vector<std::pair<T, int>> dist(
        (int)G.size(), std::make_pair(std::numeric_limits<T>::max(), -1));
    std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>,
                        std::greater<std::pair<T, int>>>
        que;
    que.push(std::make_pair(start_val, start));
    dist[start].first = start_val;
    while (!que.empty()) {
        T dist_q = que.top().first, vertex = que.top().second;
        que.pop();
        if (dist[vertex].first < dist_q) {
            continue;
        }
        for (Edge<T> edge : G[vertex]) {
            // dist[vertex] is not max()
            if (dist[edge.to()].first > dist[vertex].first + edge.cost()) {
                dist[edge.to()].first = dist[vertex].first + edge.cost();
                dist[edge.to()].second = vertex;
                que.push(std::make_pair(dist[edge.to()].first, edge.to()));
            }
        }
    }

    return dist;
}
}  // namespace lib

#line 2 "src/Graph/dijkstra.hpp"

#include <cassert>
#include <limits>
#include <queue>
#include <vector>

#line 2 "src/Graph/Graph.hpp"

#line 4 "src/Graph/Graph.hpp"
#include <iostream>
#line 7 "src/Graph/Graph.hpp"

namespace lib {
template <class T>
struct Edge {
   public:
    Edge() : _to(-1), _cost(0) {}
    Edge(int to, T cost = 1) : _to(to), _cost(cost) {}
    int to() { return _to; }
    T cost() { return _cost; }
    void change_cost(const T& val) { _cost = val; }
    void change_to(const int& val) { _to = val; }

   private:
    int _to;
    T _cost;
};

template <class T = long long>
class Graph {
   public:
    Graph(int N) : N(N), G(N) {}
    void add_edge(int u, int v, T cost = 1) {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        G[u].push_back(Edge<T>(v, cost));
        return;
    }

    void erase_edge(int u, int idx) {
        assert(0 <= u && u < N);
        assert(0 <= idx && idx < (int)G[u].size());
        swap_edge(G[u][idx], G[u].back());
        G[u].pop_back();
        return;
    }

    void erase_edge_vertex(int u, int v) {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        int last = (int)(G[u].size() - 1);
        for (int i = 0; i < (int)(G[u].size()); i++) {
            if (i > last) {
                break;
            }
            if (G[u][i].to() == v) {
                swap_edge(G[u][i], G[u][last]);
                last--;
            }
        }

        for (int i = last; i < (int)(G[u].size()); i++) {
            G[u][i].pop_back();
        }
        return;
    }

    const std::vector<Edge<T>>& operator[](int i) const {
        assert(0 <= i && i < N);
        return G[i];
    }

    std::size_t size() const { return G.size(); }

   private:
    const int N;
    std::vector<std::vector<Edge<T>>> G;
    void swap_edge(Edge<T>& e1, Edge<T>& e2) {
        int to1 = e1.to();
        e1.change_to(e2.to());
        e2.change_to(to1);

        T cost1 = e1.cost;
        e1.change_cost(e2.cost());
        e2.change_ost(cost1);
        return;
    }
};
}  // namespace lib
#line 9 "src/Graph/dijkstra.hpp"

namespace lib {
template <class T = long long>
std::vector<std::pair<T, int>> dijkstra(int start, const Graph<T>& G,
                                        T start_val = 0) {
    assert(0 <= start && start < (int)G.size());
    // 距離 と どこからかを保持
    std::vector<std::pair<T, int>> dist(
        (int)G.size(), std::make_pair(std::numeric_limits<T>::max(), -1));
    std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>,
                        std::greater<std::pair<T, int>>>
        que;
    que.push(std::make_pair(start_val, start));
    dist[start].first = start_val;
    while (!que.empty()) {
        T dist_q = que.top().first, vertex = que.top().second;
        que.pop();
        if (dist[vertex].first < dist_q) {
            continue;
        }
        for (Edge<T> edge : G[vertex]) {
            // dist[vertex] is not max()
            if (dist[edge.to()].first > dist[vertex].first + edge.cost()) {
                dist[edge.to()].first = dist[vertex].first + edge.cost();
                dist[edge.to()].second = vertex;
                que.push(std::make_pair(dist[edge.to()].first, edge.to()));
            }
        }
    }

    return dist;
}
}  // namespace lib

Back to top page