導入

グラフ上の特定の頂点からその他全ての頂点までの最短経路を得ることができます。
いわゆる単一始点最短経路問題で使用される頻出アルゴリズムです。

計算量はO(Elog⁡V)O(E\log{V})

イメージ

例として以下のようなグラフを用意しました。
ダイクストラ法を用いてsを始点とした頂点a~gまでの最短距離を求めるイメージを掴みましょう。

alt text

ダイクストラ法では始点から各頂点までの現時点での最短距離をdist配列で管理します。
また、次に確定すべき候補をpq（優先度付きキュー）で管理します。
pqには{dist[v], v}のペアを入れ、始点からの累積距離が小さい順に取り出します。
{dist[v],v}とは、現時点で到達可能な頂点の集合のうちその距離が最短な頂点vと、始点からの距離dist[v]を表します。

最初に始点となるsにdist[s]=0をセットし、その他の頂点にはdist[v]=∞をセットします。
pqには{0, s}を入れて探索を始めます(距離0でsに到達という意味)。

alt text

pqから{0, s}を取り出します。
sの隣接頂点a, c, eについて、dist[s]+辺の重みを計算し各頂点の現時点の最短距離(∞)と比較してdistを更新します。

  • dist[a] = 0+1 = 1
  • dist[c] = 0+3 = 3
  • dist[e] = 0+5 = 5

更新した頂点をpqに追加します。

pq: {1,a}、{3,c}、{5,e}

pqから最小の{1, a}を取り出し、aを確定します。

alt text

aの隣接頂点c, bについてdistの更新を試みます。

  • dist[c] = 1+1 = 2
  • dist[b] = 1+2 = 3

更新前のpq： {3,c}、{5,e}
更新後のpq： {2,c}、{3,b}、{3,c}、{5,e}

pqから最小の{2, c}を取り出し、cを確定します。

alt text

cの隣接頂点dについてdistの更新を試みます。

  • dist[d] = 2+4 = 6

更新前のpq： {3,b}、{3,c}、{5,e}
更新後のpq： {3,b}、{3,c}、{5,e}、{6,d}

pqから{3, b}を取り出し、bを確定します。

alt text

bから伸びる未探索の辺はないため追加はありません。

更新前のpq： {3,c}、{5,e}、{6,d}
更新後のpq： {3,c}、{5,e}、{6,d}

続いてpqから{3, c}を取り出しますが、3は現時点でのdist[c]=2より大きいため最短距離ではありません。
よってスルーします。
今回も辺の追加はないです。

更新前のpq： {5,e}、{6,d}
更新後のpq： {5,e}、{6,d}

alt text

pqから{5, e}を取り出し、eを確定します。
eの隣接頂点fについてdistの更新を試みます。

  • dist[f] = 5+3 = 8

更新前のpq： {6,d}
更新後のpq： {6,d}、{8,f}

alt text

pqから{6, d}を取り出し、dを確定します。
dの隣接頂点gについてdistの更新を試みます。

  • dist[g] = 6+2 = 8

更新前のpq： {8,f}
更新後のpq： {8,f}、{8,g}

alt text

pqから{8, f}を取り出し、fを確定します。
fの隣接頂点gについてdistの更新を試みます。

  • dist[g] = 8+4 = 12

更新前のpq： {8,g}
更新後のpq： {8,g}、{12,g}

alt text

pqから{8, g}を取り出し、gを確定します。
gの隣接頂点fはすでに確定済みのためスキップします。

更新前のpq： {8,g}、{12,g}
更新後のpq： {12,g}

alt text

pqから{12, g}を取り出しますが、12は現時点でのdist[g]=8より大きいため最短距離ではありません。

更新前のpq： {12,g}
更新後のpq： {}

pqが空になったためこれで終了です。

alt text

お疲れ様でした。長かったと思いますがこれで全ての処理を追い終わりました。
最初に計算量はO(Elog⁡V)O(E\log{V})といいましたが、全ての頂点を探索する様子(O(E)O(E))が掴めたと思います。
O(log⁡V)O(\log{V})の出所はpriority_queueへの操作です。

実装例

今見てきた流れをそのまま書きましょう。

int main(){
  int V,E;
  cin>>V>>E;

  vector<vector<pair<int,int>>>graph(V); //{隣接頂点, 重み}が入る
  for(int i=0;i<E;i++){
    // uとvの間に重みwの辺を張る入力を想定
    int u,v,w;
    cin>>u>>v>>w;
    graph[u].push_back({v,w});
    graph[v].push_back({u,w});
  }

  int s=0;
  vector<int>dist(V,INT_MAX); //頂点数はV個, それぞれを実質的な∞で初期化
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>pq; //pq.topで最小値が得られます

  dist[s]=0; //始点sまでの距離は0なので
  pq.push({0,s});

  while(!pq.empty()){
    auto[d,v]=pq.top(); //dが距離, vが対応する頂点
    pq.pop();
    if(d>dist[v])continue; //今見ている辺を使用するルートが, 現時点での最小値dist[v]より大きければそのルートは使用しない
    for(auto[cost,u]:graph[v]){
      if(dist[v]+cost<dist[u]){
        dist[u]=dist[v]+cost;
        pq.push({dist[u],u});
      }
    }
  }

  for(int i=0;i<V;i++){
    cout<<"dist["<<i<<"]="<<dist[i]<<endl;
  }
}

最後に

上記の実装例は本当にシンプルなものなのでわかりやすいと思います。
自分で書いてみて理解を深めてください。