最短経路問題

蟻本等の内容を復習していく。

Bellman-Ford法

頂点sから頂点iまでの仮の最短距離をd[i]とする
0: d[s]=0, d[i(≠s)]=INF とする
1: u,v∈V に対してd[v]=min(d[v],d[u]+w(u,v))で更新。更新できなくなったら終了
step1がV回実行されても終了しない場合、負の閉路が存在することが分かる。

計算量はstep1の操作がO(V)で高々E回実行されるからO(VE)

//Bellman-Ford algorithm
struct edge{int from,to,cost;};
const int INF=1e9;

bool BellmanFord(vector<vector<edge> > &g,vector<int> &d,vector<int> &prev,int s){
    int V=g.size();
    for(int i=0;i<V;i++) d[i]=(i==s)?0:INF;
    for(int i=0;i<V;i++){
        bool update=false;
        for(int u=0;u<V;u++){
            for(int j=0;j<g[u].size();j++){
                edge e=g[u][j];
                if(d[e.to]>d[e.from]+e.cost){
                    update=true;
                    d[e.to]=d[e.from]+e.cost;
                    prev[e.to]=e.from;
                }
            }
        }
        if(!update) return true;
    }
    return false;   //there is a negative loop
}
//
vector<int> buildPath(vector<int> &prev,int t){
    vector<int> res;
    for(int v=t;v>=0;v=prev[v]){
        res.push_back(v);
    }
    reverse(res.begin(),res.end());
    return res;
}

Dijkstra法

頂点sから頂点iまでの仮の最短距離をd[i]とする。Bellman-Ford法では次に使う頂点の探索に無駄があったが、Dijlkstra法では(仮の最短距離、頂点)の候補をヒープで管理することで高速で計算できる。但し、負の辺が含まれる場合は使うことができない。

計算量は、次に使う頂点の探索がO(logV)で全体ではO(E logV)

//Dijkstra
struct edge{int from,to,cost;};
const int INF=1e9;

void Dijkstra(vector<vector<edge> > &g,vector<int> &d,int s){
    int V=g.size();
    for(int i=0;i<V;i++) d[i]=(i==s)?0:INF;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que;
    que.push(make_pair(0,s));
    while(!que.empty()){
        pair<int,int> p=que.top();que.pop();
        int u=p.second;
        if(d[u]<p.first) continue;
        for(int i=0;i<g[u].size();i++){
            edge e=g[u][i];
            if(d[e.to]>d[e.from]+e.cost){
                d[e.to]=d[e.from]+e.cost;
                que.push(make_pair(d[e.to],e.to));
            }
        }
    }
}