「ダイクストラ法」の編集履歴（バックアップ）一覧はこちら

「ダイクストラ法」(2007/07/03 (火) 19:26:31) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

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;
    }
  }
 }

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;
    }
  }
 }