(単一ソース最短)Bellman-Fordアルゴリズム
1083 ワード
Bellman-Fordアルゴリズムは負の重みを含む単一ソースの最短パスを求めるアルゴリズムであり,効率は低いが,コードは書きやすい.その原理は、弛緩を継続的に行い(原文はこう書いてあるが、なぜ弛緩と呼ぶのか、議論が大きい)、弛緩のたびに各辺を更新し、n-1回弛緩した後に更新できると説明図に負のループがあるため、結果が得られず、そうでなければ完成する.Bellman-Fordアルゴリズムには小さな最適化があります.緩和のたびに識別flagが設定され、初期値はFALSEであり、エッジ更新があればTRUEに割り当てられ、最終的にはFALSEであれば直接終了に成功します.
struct edge {
int from,to;
int cost;
};
edge es[MAXE];
int d[MAXV]; // d[i] d[start] i
int v, e; // ,
void Bellman_Ford(int s) {
fill(d + 1, d + v + 1, INF);
d[s] = 0;
for (int i = 1; i <= v; ++i) {
bool update = false;
for (int j = 0; j < e; ++j) {
if (d[es[j].from] != INF) {
d[es[j].to] = min(d[es[j].to], d[es[j].from] + es[j].cost);
update = true;
}
}
if (!update)
break;
}
bool flag = false;
for (int i = 0; i < es.size(); ++i) {
if (d[es[i].to] > d[es[i].from] + es[i].cost) {
flag = true;
break;
}
}
if (flag)
cout << " ";
}