怎么制作网站视频教程步骤,优化设计答案,珠海企业集团网站建设,做网站用空间好还是服务器好1. 前言
前文的迪杰斯特拉算法不能求解有负边的图的最短路径的问题。而此文的Bellman-Ford可以处理含负权边的图算法#xff0c;并且能检测出图中是否存在负环#xff08;权重和为负数的环#xff09;.
2. 基本思想
1. 初始化#xff1a;
对于所有顶点 v ∈ V \ {s}并且能检测出图中是否存在负环权重和为负数的环.
2. 基本思想
1. 初始化
对于所有顶点 v ∈ V \ {s}除了起点 s设其到起点的距离为无穷大表示不可达。起点 s 到自身的距离设为 0。 2. 松弛操作
遍历图中的每条边 (u, v) ∈ E执行松弛操作 Relax(u, v, w)。松弛操作尝试通过边 (u, v) 更新从起点 s 到顶点 v 的已知最短距离。如果存在一条从起点 s 到顶点 u 的更短路径并且这条路径加上边 (u, v) 的权重小于目前记录的从起点 s 到顶点 v 的距离则更新顶点 v 的距离值。这个过程需要重复进行 |V| - 1 次V 是顶点集。因为在没有负权环的情况下任何从起点到某个顶点的最短路径最多包含 |V| - 1 条边。
3. 检查负权环 在进行了 |V| - 1 轮松弛操作之后再进行一轮松弛操作。如果在这个过程中仍然能够进一步减少某个顶点的距离值那么说明图中存在一个可以被利用来无限降低路径成本的负权环。
3. 顶点类代码
public class Vertex {// 顶点的名字用来区分顶点String name;// 与该顶点有关的边的集合ListEdge edges;// 判断是否已经被遍历boolean visited false;// 初始距离为无穷大int dist INF;// INF表示无穷大final static int INF Integer.MAX_VALUE;// 该顶点在最短路径中的前一个顶点Vertex prev null;public Vertex(String name) {this.name name;}public String getName() {return name;}
}
顶点图 4. Bellman-Ford算法代码
public class BellmanFord {public static void main(String[] args) {Vertex v1 new Vertex(1);Vertex v2 new Vertex(2);Vertex v3 new Vertex(3);Vertex v4 new Vertex(4);v1.edges new ArrayList();v1.edges.add(new Edge(v2, 2));v1.edges.add(new Edge(v3, 1));v2.edges new ArrayList();v2.edges.add(new Edge(v3, -2));v3.edges new ArrayList();v3.edges.add(new Edge(v4, 1));v4.edges new ArrayList();ListVertex graph new ArrayList();graph.add(v1);graph.add(v2);graph.add(v3);graph.add(v4);// v1作为起始点bellmanford(graph, v1);}public static void bellmanford(ListVertex graph, Vertex source){// 将起始点的距离设置为0其余点的距离都是无穷大source.dist 0;int size graph.size();// 进行 顶点数-1 次处理for(int k 0; k size - 1; k) {// 遍历所有的边for(Vertex v : graph){for(Edge e : v.edges){// 处理每条边if(v.dist ! Integer.MAX_VALUE v.dist e.weight e.linked.dist){e.linked.dist v.dist e.weight;e.linked.prev v;}}}}for(Vertex v : graph){System.out.println(v v.name v.dist);}}
}打印的结果
v1 0
v2 2
v3 0
v4 1
