Dijkstra
(Graph/Dijkstra.cpp)

• View this file on GitHub
• Last update: 2022-03-14 18:12:26+09:00

説明

重み付き（有向）グラフにおける最短経路問題を解くアルゴリズム。グラフの重みは非負でないといけない。負の重みの辺がある場合は Bellman-Ford法 を使う。

• vector<T> dijkstra(int node,vector<vector<Edge<T>> graph,int start) : 隣接リストで表現された node 頂点のグラフ graph において、頂点 start から各頂点への最短距離を求める。返り値として長さ node の配列 dist が返される。辺の本数を $edge$ とおくと計算量 $O(edge + node \log node)$
  • dist[i] = 頂点 s から頂点 i までの最短距離、ただしパスが存在しない場合は std::numeric_limits<T>::max() が格納される
• vector<int> get_path(int t) : 頂点 start から頂点 t までの最短経路の内 1 つを列挙する。計算量 $O(node)$

Verified with

• Test/AOJ/Dijkstra.test.cpp

Code

template<typename T>
struct Edge {
    int to;
    T cost;
};

std::vector<int> pre;

template<typename T>
std::vector<T> dijkstra(const int& node,const vector<vector<Edge<T>>>& graph,const int& start) {
    std::priority_queue<pair<T,int>,vector<pair<T,int>>,greater<pair<T,int>>> que;
    vector<T> dist(node,numeric_limits<T>::max());
    pre = vector<int>(node,-1);
    dist[start] = 0;
    que.push({0,start});

    while(!que.empty()) {
        auto [cost,v] = que.top();
        que.pop();
        if(dist[v] < cost) continue;
        for(const auto& [to,d]:graph[v]) {
            if(dist[to] > dist[v] + d) {
                dist[to] = dist[v] + d;
                pre[to] = v;
                que.push({dist[to],to});
            }
        }
    }

    return dist;
}

vector<int> GetPath(int t) {
    vector<int> path;

    while(t != -1) {
        path.push_back(t);
        t = pre[t];
    }

    reverse(path.begin(),path.end());
    return path;
}

#line 1 "Graph/Dijkstra.cpp"
template<typename T>
struct Edge {
    int to;
    T cost;
};

std::vector<int> pre;

template<typename T>
std::vector<T> dijkstra(const int& node,const vector<vector<Edge<T>>>& graph,const int& start) {
    std::priority_queue<pair<T,int>,vector<pair<T,int>>,greater<pair<T,int>>> que;
    vector<T> dist(node,numeric_limits<T>::max());
    pre = vector<int>(node,-1);
    dist[start] = 0;
    que.push({0,start});

    while(!que.empty()) {
        auto [cost,v] = que.top();
        que.pop();
        if(dist[v] < cost) continue;
        for(const auto& [to,d]:graph[v]) {
            if(dist[to] > dist[v] + d) {
                dist[to] = dist[v] + d;
                pre[to] = v;
                que.push({dist[to],to});
            }
        }
    }

    return dist;
}

vector<int> GetPath(int t) {
    vector<int> path;

    while(t != -1) {
        path.push_back(t);
        t = pre[t];
    }

    reverse(path.begin(),path.end());
    return path;
}

Back to top page