单源点最短路径(Bellman-Ford)原理及js实现
文章目录
1. 说明
Bellman-Ford算法运行结束后,会得到从源节点 s 到其它所有节点的最短路径,同时得到每个节点的前驱节点,Bellman-Ford不能包含负权回路如图 1.1 但可以包含图 1.2,这里所说的负权环路是指环路的权值总和为正或为负
图 1.1
图 1.2
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;
3. js中如何表示无穷大
在全局使用 Infinity 来表示正无穷大,用 -Infinity 表示负无穷大,同时可以使用 Number.POSITIVE_INFINITY 表示正无穷,用Number.NEGATIVE_INFINITY 表示负无穷,这几个常量都可以与其它类型的数字比较大小,在 Number中还有其它的常量,读者可以在新版的浏览器控制台 执行 console.dir(Number) 去查看
4. 相关数据结构及初始化算法的输入数据
//节点数据结构
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. Bellman-Ford算法
- 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 ,为一个具体的值
6. 完整代码
输入图为 图 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);
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论