摘要：說明算法運行結束后，會得到從源節點到其它所有節點的最短路徑，同時得到每個節點的前驅節點，不能包含負權回路如圖但可以包含圖，這里所說的負權環路是指環路的權值總和為正或為負圖圖松弛操作概念松弛操作針對的操作對象是圖中的邊，對圖中任意一條邊，

Bellman-Ford算法運行結束后，會得到從源節點 s 到其它所有節點的最短路徑，同時得到每個節點的前驅節點，Bellman-Ford不能包含負權回路如圖 1.1 但可以包含圖 1.2，這里所說的負權環路是指環路的權值總和為正或為負

圖 1.1

圖 1.2

2.1. 概念

松弛操作針對的操作對象是圖中的邊，對圖中任意一條邊e=(u,v)，假設在對e進行松弛之前，已經知道從源節點s到u的最短估計距離u.d，從源點到v的最短估距離v.d，同時邊e的權重為w，松弛操作就是更新節點v的最短估計距離v.d = min{v.d, u.d + w}, 由于初始狀態是，所有節點的最短估計路徑都設為 Infinity 即無窮大，所以在任意時刻，u.d和v.d都是存在的

2.2. 舉例

初始時，v1,v2,v3,v4四個節點的最短估計路徑都為 Infinity ，求解從v1節點到其它所有節點的最短路徑距離，所以將v1.d設置為0

圖 2.2

對邊(v1,v2)進行松弛 有 v1.d = 0,v2.d = Infinity,w(v1,v2) = 1; 所以v2.d被更新為 v2.d = v1.d + w(v1,v2) = 1;

對邊(v1,v3)進行松弛 有 v1.d = 0,v3.d = Infinity,w(v1,v3) = 3; 所以v3.d被更新為 v3.d = v1.d + w(v1,v3) = 3;

對邊(v2,v4)進行松弛 有 v2.d = 1,v4.d = Infinity,w(v2,v4) = 5; 所以v4.d被更新為 v4.d = v2.d + w(v2,v4) = 6;

對邊(v3,v4)進行松弛 有 v3.d = 3,v4.d = 6,w(v3,v4) = 1; 所以v4.d被更新為 v4.d = v3.d + w(v3,v4) = 4;

在全局使用 Infinity 來表示正無窮大，用 -Infinity 表示負無窮大，同時可以使用 Number.POSITIVE_INFINITY 表示正無窮，用Number.NEGATIVE_INFINITY 表示負無窮，這幾個常量都可以與其它類型的數字比較大小，在 Number中還有其它的常量，讀者可以在新版的瀏覽器控制臺 執行 console.dir(Number) 去查看

//節點數據結構
function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.id = null; //用來標識節點
    this.data = null; //節點數據
}

//邊數據結構
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.u = null; //邊的起點節點
    this.v = null; //邊的終點節點
    this.w = null; //邊的權重
}

//圖
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.vertices = []; //圖的節點集 作為算法的輸入數據
    this.edges = []; //圖的邊集 作為算法的輸入數據
    this.refer = new Map(); //節點標識表
}
Graph.prototype = {
    constructor: Graph,
    initVertices: function(vs) {
        for (let id of vs) {
            let v = Vertex();
            v.id = id;
            this.refer.set(id, v);
            this.vertices.push(v);
        }
    },
    initEdges: function(es) {
        for (let r of es) {
            let e = Edge();
            e.u = this.refer.get(r.u);
            e.v = this.refer.get(r.v);
            e.w = r.w;
            this.edges.push(e);
        }
    }
}

var vertices = ["v1", "v2", "v3", "v4"];
var edges = [
    {u:"v1", v:"v2", w:1},
    {u:"v1", v:"v3", w:3},
    {u:"v2", v:"v4", w:5},
    {u:"v3", v:"v4", w:1},
    {u:"v4", v:"v2", w:-3}
];

var g = Graph();
g.initVertices(vertices);
g.initEdges(edges);

5.1. 算法介紹

BellmanFord算法的原理就是對輸入的所有邊都進行 |V| - 1次松弛操作，為什么是 |V| - 1次見 5.3.

5.2. 算法的js實現

 function BellmanFord(vertices, edges, source) {
    let distance = new Map(); //用來記錄從原節點 source 到某個節點的最短路徑估計值
    let predecessor = new Map(); //用來記錄某個節點的前驅節點

    // 第一步: 初始化圖
    for (let v of vertices) {
        distance.set(v, Infinity); // 初始化最短估計距離 默認無窮大
        predecessor.set(v, null); // 初始化前驅節點 默認為空
    }
    distance.set(source, 0); // 將源節點的最短路徑估計距離 初始化為0

    // 第二步: 重復松弛邊
    for (let i = 1, len = vertices.length - 1; i < len; i++) {
        for (let e of edges) {
            if (distance.get(e.u) + e.w < distance.get(e.v)) {
                distance.set(e.v, distance.get(e.u) + e.w);
                predecessor.set(e.v, e.u);
            }
        }
    }

    // 第三步: 檢查是否有負權回路 第三步必須在第二步后面
    for (let e of edges) {
        if (distance.get(e.u) + e.w < distance.get(e.v))
            return null; //返回null表示包涵負權回路
    }

    return {
        distance: distance,
        predecessor: predecessor
    }
}

5.3. 為什么第二步中的要加最外層循環，并且是 |V| - 1 次

最外層增加循環且次數為|V| - 1次，原因是對輸入的邊的順序是沒有限制的，在 2.2.節 中，我們用了四次松弛操作就找到了從節點v1到其它所有節點的最短路徑，是因為 2.2.節 中邊是按照一定的順序選取的，開始時選取的是與源節點直接相領的邊，接下來選取邊的起始節點是已經被松弛過的邊連接的終止節點，如果對邊的選取順序為 (v2,v4),(v3,v4),(v1,v2),(v1,v3) 這種情況就需要最外層的循環，并且需要兩次,考慮最壞的情況，如圖

圖 5.3

并且邊的選取順序為(v3,v4),(v2,v3),(v1,v2),這樣對于四個節點需要三次最外層的循環，即|V| - 1

在《算法導論》中，有這樣的描述：
當進行第 i 次循環時，一定包含邊 (v[i-1],v[i]), 這句話的意思時，如果存在從源節點s到v的最短路徑，那么在第i次循環結束后，節點 v[i-1].d和節點v[i].d一定不為 Infinity ，為一個具體的值

輸入圖為 圖 1.2 從 節點v1到其它所有節點的最短路徑

//節點數據結構
function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.id = null; //用來標識節點
    this.data = null; //節點數據
}

//邊數據結構
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.u = null; //邊的起點節點
    this.v = null; //邊的終點節點
    this.w = null; //邊的權重
}

//圖
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.vertices = []; //圖的節點集
    this.edges = []; //圖的邊集
    this.refer = new Map(); //節點標識表
}
Graph.prototype = {
    constructor: Graph,
    initVertices: function(vs) {
        for (let id of vs) {
            let v = Vertex();
            v.id = id;
            this.refer.set(id, v);
            this.vertices.push(v);
        }
    },
    initEdges: function(es) {
        for (let r of es) {
            let e = Edge();
            e.u = this.refer.get(r.u);
            e.v = this.refer.get(r.v);
            e.w = r.w;
            this.edges.push(e);
        }
    }
}

function BellmanFord(vertices, edges, source) {
    let distance = new Map(); //用來記錄從原節點 source 到某個節點的最短路徑估計值
    let predecessor = new Map(); //用來記錄某個節點的前驅節點

    // 第一步: 初始化圖
    for (let v of vertices) {
        distance.set(v, Infinity); // 初始化最短估計距離 默認無窮大
        predecessor.set(v, null); // 初始化前驅節點 默認為空
    }
    distance.set(source, 0); // 將源節點的最短路徑估計距離 初始化為0

    // 第二步: 重復松弛邊
    for (let i = 1, len = vertices.length - 1; i < len; i++) {
        for (let e of edges) {
            if (distance.get(e.u) + e.w < distance.get(e.v)) {
                distance.set(e.v, distance.get(e.u) + e.w);
                predecessor.set(e.v, e.u);
            }
        }
    }

    // 第三步: 檢查是否有負權回路 第三步必須在第二步后面
    for (let e of edges) {
        if (distance.get(e.u) + e.w < distance.get(e.v))
            return null; //返回null表示包涵負權回路
    }

    return {
        distance: distance,
        predecessor: predecessor
    }
}

var vertices = ["v1", "v2", "v3", "v4"];
var edges = [
    {u:"v1", v:"v2", w:1},
    {u:"v1", v:"v3", w:3},
    {u:"v2", v:"v4", w:5},
    {u:"v3", v:"v4", w:1},
    {u:"v4", v:"v2", w:-3}
];

var g = Graph();
g.initVertices(vertices);
g.initEdges(edges);

var r = BellmanFord(g.vertices, g.edges, g.vertices[0]);
console.log(r);