單源點(diǎn)最短路徑(Bellman-Ford)原理及js實(shí)現(xiàn)

Michael_Lin 發(fā)布于2019-08-21 18:37 / 955人閱讀

摘要：說(shuō)明算法運(yùn)行結(jié)束后，會(huì)得到從源節(jié)點(diǎn)到其它所有節(jié)點(diǎn)的最短路徑，同時(shí)得到每個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，不能包含負(fù)權(quán)回路如圖但可以包含圖，這里所說(shuō)的負(fù)權(quán)環(huán)路是指環(huán)路的權(quán)值總和為正或?yàn)樨?fù)圖圖松弛操作概念松弛操作針對(duì)的操作對(duì)象是圖中的邊，對(duì)圖中任意一條邊，

1. 說(shuō)明

Bellman-Ford算法運(yùn)行結(jié)束后，會(huì)得到從源節(jié)點(diǎn) s 到其它所有節(jié)點(diǎn)的最短路徑，同時(shí)得到每個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，Bellman-Ford不能包含負(fù)權(quán)回路如圖 1.1 但可以包含圖 1.2，這里所說(shuō)的負(fù)權(quán)環(huán)路是指環(huán)路的權(quán)值總和為正或?yàn)樨?fù)

圖 1.1

圖 1.2

2. 松弛操作

2.1. 概念

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

2.2. 舉例

初始時(shí)，v1,v2,v3,v4四個(gè)節(jié)點(diǎn)的最短估計(jì)路徑都為 Infinity ，求解從v1節(jié)點(diǎn)到其它所有節(jié)點(diǎn)的最短路徑距離，所以將v1.d設(shè)置為0

圖 2.2

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

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

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

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

3. js中如何表示無(wú)窮大

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

4. 相關(guān)數(shù)據(jù)結(jié)構(gòu)及初始化算法的輸入數(shù)據(jù)

//節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)
function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.id = null; //用來(lái)標(biāo)識(shí)節(jié)點(diǎn)
    this.data = null; //節(jié)點(diǎn)數(shù)據(jù)
}

//邊數(shù)據(jù)結(jié)構(gòu)
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.u = null; //邊的起點(diǎn)節(jié)點(diǎn)
    this.v = null; //邊的終點(diǎn)節(jié)點(diǎn)
    this.w = null; //邊的權(quán)重
}

//圖
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.vertices = []; //圖的節(jié)點(diǎn)集 作為算法的輸入數(shù)據(jù)
    this.edges = []; //圖的邊集 作為算法的輸入數(shù)據(jù)
    this.refer = new Map(); //節(jié)點(diǎn)標(biāo)識(shí)表
}
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. Bellman-Ford算法

5.1. 算法介紹

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

5.2. 算法的js實(shí)現(xiàn)

 function BellmanFord(vertices, edges, source) {
    let distance = new Map(); //用來(lái)記錄從原節(jié)點(diǎn) source 到某個(gè)節(jié)點(diǎn)的最短路徑估計(jì)值
    let predecessor = new Map(); //用來(lái)記錄某個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)

    // 第一步: 初始化圖
    for (let v of vertices) {
        distance.set(v, Infinity); // 初始化最短估計(jì)距離 默認(rèn)無(wú)窮大
        predecessor.set(v, null); // 初始化前驅(qū)節(jié)點(diǎn) 默認(rèn)為空
    }
    distance.set(source, 0); // 將源節(jié)點(diǎn)的最短路徑估計(jì)距離 初始化為0

    // 第二步: 重復(fù)松弛邊
    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);
            }
        }
    }

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

    return {
        distance: distance,
        predecessor: predecessor
    }
}

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

最外層增加循環(huán)且次數(shù)為|V| - 1次，原因是對(duì)輸入的邊的順序是沒(méi)有限制的，在 2.2.節(jié) 中，我們用了四次松弛操作就找到了從節(jié)點(diǎn)v1到其它所有節(jié)點(diǎn)的最短路徑，是因?yàn)?2.2.節(jié) 中邊是按照一定的順序選取的，開(kāi)始時(shí)選取的是與源節(jié)點(diǎn)直接相領(lǐng)的邊，接下來(lái)選取邊的起始節(jié)點(diǎn)是已經(jīng)被松弛過(guò)的邊連接的終止節(jié)點(diǎn)，如果對(duì)邊的選取順序?yàn)?(v2,v4),(v3,v4),(v1,v2),(v1,v3) 這種情況就需要最外層的循環(huán)，并且需要兩次,考慮最壞的情況，如圖

圖 5.3

并且邊的選取順序?yàn)?b>(v3,v4),(v2,v3),(v1,v2),這樣對(duì)于四個(gè)節(jié)點(diǎn)需要三次最外層的循環(huán)，即|V| - 1

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

6. 完整代碼

輸入圖為 圖 1.2 從節(jié)點(diǎn)v1到其它所有節(jié)點(diǎn)的最短路徑

//節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)
function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.id = null; //用來(lái)標(biāo)識(shí)節(jié)點(diǎn)
    this.data = null; //節(jié)點(diǎn)數(shù)據(jù)
}

//邊數(shù)據(jù)結(jié)構(gòu)
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.u = null; //邊的起點(diǎn)節(jié)點(diǎn)
    this.v = null; //邊的終點(diǎn)節(jié)點(diǎn)
    this.w = null; //邊的權(quán)重
}

//圖
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.vertices = []; //圖的節(jié)點(diǎn)集
    this.edges = []; //圖的邊集
    this.refer = new Map(); //節(jié)點(diǎn)標(biāo)識(shí)表
}
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(); //用來(lái)記錄從原節(jié)點(diǎn) source 到某個(gè)節(jié)點(diǎn)的最短路徑估計(jì)值
    let predecessor = new Map(); //用來(lái)記錄某個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)

    // 第一步: 初始化圖
    for (let v of vertices) {
        distance.set(v, Infinity); // 初始化最短估計(jì)距離 默認(rèn)無(wú)窮大
        predecessor.set(v, null); // 初始化前驅(qū)節(jié)點(diǎn) 默認(rèn)為空
    }
    distance.set(source, 0); // 將源節(jié)點(diǎn)的最短路徑估計(jì)距離 初始化為0

    // 第二步: 重復(fù)松弛邊
    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);
            }
        }
    }

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

    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);