Day60 图论part10
本日大家会感受到 Bellman_ford 算法系列在差别场景下的应用。建议依然是：一刷的时候，能理解 原理，知道Bellman_ford 办理差别场景的题目 ，照着代码随想录能抄下来代码就好，就算达标。 二刷的时候自己尝试独立去写，三刷的时候 才能有肯定深度理解各个最短路算法。
Bellman_ford 队列优化算法（又名SPFA）
代码随想录
import java.util.*;
public class Main{
public static void main (String[] args) {
//对所有的边松弛n-1次
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
List<List<Edge>> graph = new ArrayList<>(n+1);
for(int i = 0; i <= n; i++){
graph.add(new ArrayList<>());
}
for(int i = 0; i < m; i++){
int start = scanner.nextInt();
int end = scanner.nextInt();
int val = scanner.nextInt();
graph.get(start).add(new Edge(start, end, val));
}
int[] minDist = new int;
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist = 0;
Deque<Integer> queue = new ArrayDeque<>();
boolean[] isVisited = new boolean;
queue.add(1);
isVisited = true;
while(!queue.isEmpty()){
int start = queue.remove();
//取出队列的时候，要取消标记，这样保证有其他路径对该节点进行更新，我们只要保证节点不被重复加入队列即可
isVisited = false;
for(Edge edge : graph.get(start)){
if(minDist + edge.val < minDist){
minDist = minDist + edge.val;
if(!isVisited){
queue.add(edge.end);
isVisited = true;
}
}
}
}
if(minDist == Integer.MAX_VALUE){
System.out.println("unconnected");
}else{
System.out.println(minDist);
}
}
}
class Edge{
int start;
int end;
int val;
public Edge(int start, int end, int val){
this.start = start;
this.end = end;
this.val = val;
}
}总结
1.普通的Bellman_ford算法其实是每次都对所有的边都举行一次松懈，但其实但真正有效的松懈，是基于已经盘算过的节点在做的松懈。所以我们每次松懈只必要基于上一次松懈更新过的节点，以该节点作为出发节点对毗连的边就行。那我们就可以使用队列来纪录上一次松懈更新过的节点，把这些节点依次加入到队列内里，然后又取出来处理惩罚。
2.队列内里存储的是每条边的起点，我们必要根据这些起点，找到边，所以这样传统的邻接表来存储图是最好的List<List<Edge>> graph = new ArrayList<>(n+1);
3.然后在while循环内里，还有一些地方和之前的处理惩罚不一样，我们必要使用isVisited[]数组来判断节点是否在队列内里&#x
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]