1、说明Bellman-Ford算法运行后，会得到源节点s到所有其他节点的最短路径，同时会得到每个节点的前驱节点。Bellman-Ford不能包含如图1.1所示的负权重循环但可以包含图1.2，这里所说的负权重循环是指循环的权重之和为正或负=(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.d=3,v4.d=6,w(v3,v4)=1放松边缘(v3,v4)；所以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.相关数据结构和初始化算法的输入数据//节点数据结构函数Vertex(){if(!(thisinstanceofVertex))returnnewVertex();这个.id=null；//用于标识节点this.data=null;//节点数据}//边缘数据结构functionEdge(){if(!(thisinstanceofEdge))returnnewEdge();这个。你=空；//边的起始节点this.v=null;//边的结束节点this.w=null;//边的权重}//GraphfunctionGraph(){if(!(thisinstanceofGraph))returnnewGraph();this.vertices=[];//图的节点集作为算法的输入数据this.edges=[];//图的边集作为算法的输入数据this.refer=newMap();//节点标识表}Graph.prototype={constructor:Graph,initVertices:function(vs){for(letidofvs){letv=Vertex();v.id=id;this.refer.set(id,v);this.vertices.push(v);}},initEdges:function(es){for(letrofes){lete=Edge();e.u=this.refer.get(r.u);e.v=这个。参考。得到（r.v）；e.w=r.w;this.edges.push(e);}}}varvertices=['v1','v2','v3','v4'];varedges=[{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}];varg=Graph();g.initVertices(顶点);g.initEdges(边);5。贝尔曼-福特算法5.1。算法介绍BellmanFord算法的原理是执行|V|js实现函数BellmanFord(vertices,edges,source){letdistance=newMap();//用于记录从原始节点源到某个节点的最短路径的估计值letpredecessor=newMap();//用来记录一个节点的前驱节点//Step1:Initializethegraphfor(letvofvertices){distance.set(v,Infinity);//初始化最短估计距离defaultinfinitypredecessor.set(v,null);//初始化前驱节点默认为空}distance.set(source,0);//将源节点的估计最短路径距离初始化为0//步骤2：重复松弛边for(leti=1,len=vertices.length-1;i
