ダイクストラ法 - Programming @ wiki

1. 配列cost を用意する。cost の大きさは町の数と同じである。配列cost に最大値(INT_MAX)を入れておく。ただし、スタートの町だけは、cost の値を0 にしておく。
2. 配列usedFlag のすべての要素を0 で初期化しておく。これはまだ使用していないことを意味する。
3. すべての町i の中で、usedFlag[i]が0 で、かつ最小のcost[i]を持つ町x を探す。
4. 町x が見つからないか、町x のcost[i]が大きな値(INT_MAX)ならば、終了。
5. 町x を使用済みとする。（usedFlag[x] ← 1）
6. 町x を経由していける場所のコストを更新する。すなわち、町i に対して、cost[i] > cost[x]+町x から町i へのコストならば、cost[i] = cost[x]+町x から町i へのコストとする。町i には町x からきたことを記録する。
7. 3に戻る。

void dijkstra( istream &is ) {
   int start, end;
   int usedFlag[matMax];
   int cost[matMax];
   int beforeCity[matMax];
 while( true ) {
   if ( !(is >> start >> end ) ) break;
 
 // 初期化
    for( i=0; i<matMax; i++ ) usedFlag[i] = 0;
   for(i=0; i<matNum; i++ ) cost[i] = INT_MAX;
 //最後の町は訪れたことにする  
   cost[end] = 0;
   
   while( true ) {
 // 使用済みでない最小の町を求める
      int minVal = INT_MAX;
     int min;
     for( i=0; i<matNum; i++ ) {
        if ( usedFlag[i] == 0 && minVal > cost[i] ) {
           min = i;
           minVal = cost[i];
        }
     }
 //終了チェック
      if ( minVal == INT_MAX ) break;
 // 使用済にする
      usedFlag[min] = 1;
 // 町min から行ける町のcost を更新
      for( i=0; i<matNum; i++ ) {
         if ( mat[min][i] && cost[min]+mat[min][i] < cost[i] ) {
            cost[i] = cost[min]+mat[min][i];
            beforeCity[i] = min;
      }
   }
 // 結果の出力
   bool firstFlag = true;
   while(true) {
      if ( firstFlag ) firstFlag = false;
      else cout << " ";
      cout << (start+1);
      if ( start == end ) break;
      start = beforeCity[ start ];
      cout << endl;
   }
 }
}