C++によるダイクストラ法

An article by yuyak    No Comments

ダイクストラ法とは

ダイクストラ法はグラフ上の2頂点間の最短経路を効率的に求めるアルゴリズムで、1959年エドガー・ダイクストラによって考案された。 応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。 なお最短経路の推定値を事前に知っているときは、ダイクストラ法の改良版であるA*アルゴリズムを用いて、より効率的 に最短経路を求める事ができる。

ダイクストラ法 – Wikipediaより

実装

もうちょっと綺麗に書いた方がいいなぁ。。

#include <vector>

using namespace std; 

#define MAX_VALUE 999999
int n = 6;
vector<vector<int> > graph(n, vector<int>(n));

void setGraph(int x, int y, int distance) {
  graph[y][x] = distance;
  graph[x][y] = distance;
}

void readGraph() {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      graph[i][j] = MAX_VALUE;
  setGraph(0, 1, 6);
  setGraph(0, 2, 10);
  setGraph(1, 2, 2);
  setGraph(1, 3, 8);
  setGraph(2, 4, 4);
  setGraph(3, 4, 1);
  setGraph(3, 5, 1);
  setGraph(4, 5, 3);
}

void dijkstra(void) {
  int min = MAX_VALUE;

  int preview[6];
  bool visited[6];
  int distance[6];

  for (int i = 0; i < n; i++)
    visited[i] = false, distance[i] = MAX_VALUE;
  distance[0] = 0;
  preview[0] = 0; 

  int next = 0, p = 0;

  do {
    p = next;
    visited[p] = true;
    min = MAX_VALUE;

    for (int j = 0; j < n; j++) {
      if (visited[j]) continue;
      if (graph[p][j] < MAX_VALUE &&
          distance[p] + graph[p][j] < distance[j]){
        distance[j] = distance[p] + graph[p][j];
        preview[j] = p;
      }
      if (distance[j] < min) {
        next = j;
        min = distance[j];
      }
    }
  } while (min < MAX_VALUE);

  cout << "point" << " preview" << " distance" << endl;
  for (int i = 0; i < n; i++) {
    cout << i << "      " << preview[i] << "        " << distance[i] << endl;
  }
}

int main() {
  readGraph();
  dijkstra();
  return 0;
}

実行結果

point preview distance
0      0        0
1      0        6
2      1        8
3      4        13
4      2        12
5      3        14

参考リンク

1. ダイクストラ法（最短経路問題）

参考文献

Javaによるアルゴリズム事典 技術評論社 2003-05 売り上げランキング : 202576 Amazonで詳しく見る