Help us understand the problem. What is going on with this article?

最短経路問題-ベルマンフォード法を学ぶ

最短経路問題

最短経路問題とは、ある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);

参考文献

プログラミングコンテストチャレンジブック [第2版]

yoshii0110
あくまで個人の見解なので、その点はご容赦下さい。
kddi
KDDIは、通信を中心に周辺ビジネスを拡大する「通信とライフデザインの融合」をより一層推進し、国内はもとよりグローバルにおいても、5G/IoT時代における新たな価値創造を実現し、お客さまの期待を超える新たな体験価値の提供を追求してまいります。
http://www.kddi.com
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away