アルゴリズムクイックリファレンス 第2版

6.5

 密グラフ用ダイクストラ法

■

173

//

未訪問節点のうち

s

から最短の節点を見つける。

//

可能な新経路を再計算して、すべての最短経路を更新する。

while (true) {

int u = -1;

int sd = numeric_limits<int>::max();

for (int i = 0; i < n; i++) {

if (!visited[i] && dist[i] < sd) {

sd = dist[i];

u = i;

}

}

if (u == -1) { break; } //

新たな経路が見つからなければ抜け出す

// u

の隣接点について、

s->u

の最良経路長＋辺

u->v

の重みが

// s->v

の最良経路よりもよいかどうか調べる。

long

を使って計算する

visited[u] = true;

for (int v = 0; v < n; v++) {

int w = weight[u][v];

if (v == u) continue;

long newLen = dist[u];

newLen += w;

if (newLen < dist[v]) {

dist[v] = newLen;

pred[v] = u;

}

}

}

delete [] visited;

}

6.5.1

 変形

メッセージを正確に伝送する確率がわかっているなら、ネットワークのある点か

ら別の点にメッセージを送る最も信頼のおける経路を求めることもできる。任意の

経路（辺の組み ...