最短経路問題
最短経路問題とは、ある2頂点が与えられたグラフの頂点を始点・終点とするとき、その頂点同士を結ぶ辺のコスト(距離)の和が最小とする問題です。
ベルマンフォード法
最短経路問題を解く手法の一つにベルマンフォード法というものがあります。
ベルマンフォード法では、始点から他のすべての頂点への最短経路を求めることができます。
アルゴリズム概要
始点 s から頂点 i への最短距離を d[i] , 頂点 i から頂点 j へのコストを Cij とすると以下の等式が成り立ちます。(ちなみにEは辺の集合です)
ちなみに、これは負の閉路が存在しないことをまずは前提(というのも負の閉路検出の方法もできるので)とし考えていきます。
なので、負の閉路が存在しなければ、最短経路は同じ頂点を通らないので、繰り返す回数の最大値は(頂点数−1)回になります。
d[i] = min{ d[j] + Cij ∣ e = (j,i) ∈ E }
式だとわからないと思うので、簡単にアルゴリズムの動きを言語化するならば下記のようになります。
1. 全ての辺に対し、その辺を通った頂点のコストが小さければ値を更新する。
2. 1のプロセスを（頂点の数-1）回行います。
実装してみよう
sample.js
// 初期化
const graph = [
[null, 1, 3, null, null, null],
[null, null, 1, 4, null, null],
[null, null, null, 1, null, null]
];
let dist = [];
for(var i = 0; i < graph.length; i++){
dist[i] = Number.POSITIVE_INFINITY;
}
dist[0] = 0;
const shortest_path = () => {
const n = graph.length;
for(var i = 1; i <= n; i++){
failOnUpdate = (i === n);
let update = false;
for(var u = 0; u < n; u++){
for(var ci = 0; ci < n; ci++){
if(!graph[u][ci]){
continue;
}
const newLen = dist[u] + graph[u][ci];
if(newLen < dist[ci]){
if(failOnUpdate){
throw new Error('負の閉路');
}
dist[ci] = newLen;
update = true;
}
}
}
if(!update){
break;
}
}
};
// 結果
shortest_path()
console.log("最短距離");
console.log(dist);