单源点最短路径(Bellman-Ford)原理及js实现

摘要：说明算法运行结束后，会得到从源节点到其它所有节点的最短路径，同时得到每个节点的前驱节点，不能包含负权回路如图但可以包含图，这里所说的负权环路是指环路的权值总和为正或为负图图松弛操作概念松弛操作针对的操作对象是图中的边，对图中任意一条边，

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