【Java数据结构】最短路径问题多源单源
迪克斯特拉算法优先队列解决实现单源最短路径问题 找到当前距离值最小的首结点，（优先队列）更新他与邻居的距离， 负边的情况无法处理，每次认为已经找到最小的点，下次不会处理。
·
一.迪克斯特拉算法
迪克斯特拉算法优先队列解决实现单源最短路径问题 找到当前距离值最小的首结点，（优先队列）更新他与邻居的距离， 负边的情况无法处理，每次认为已经找到最小的点，下次不会处理
public class dijkstra {
public static class vartex{
String name;
List <Edge> edges;
int dist=INF;
static final Integer INF=Integer.MAX_VALUE;
boolean visited;
vartex prev=null;
public vartex(String name) {
this.name = name;
}
}
static class Edge{
public Edge(vartex linked, int weight) {
this.linked = linked;
this.weight = weight;
}
vartex linked;
int weight;
}
public static void main(String[] args) {
vartex v1=new vartex("v1");
vartex v2=new vartex("v2");
vartex v3=new vartex("v3");
vartex v4=new vartex("v4");
vartex v5=new vartex("v5");
vartex v6=new vartex("v6");
v1.edges=List.of(new Edge(v3,9),new Edge(v2,7),new Edge(v6,14));
v2.edges=List.of(new Edge(v4,15));
v3.edges=List.of(new Edge(v4,11),new Edge(v6,2));
v4.edges= List.of(new Edge(v5,6));
v5.edges= List.of();
v6.edges=List.of(new Edge(v5,9));
List<vartex> graph=List.of(v1,v2,v3,v4,v5,v6);
dijkstra(graph,v1);
}
private static void dijkstra(List<vartex> graph, vartex source) {
source.dist=0;
PriorityQueue<vartex>queue=new PriorityQueue<>(Comparator.comparingInt(v->v.dist));
for (vartex v:graph){
queue.offer(v);//入队
}
while (!queue.isEmpty()) {
// for (int i = 0; i < 6; i++) {
// queue.offer(graph.get(i));
// }
// System.out.println(queue);
//1.找到当前值最小的首结点
vartex peek = queue.peek();
//2.遍历所有邻居，更新他们的距离
if(!peek.visited) {
for (Edge edge : peek.edges) {
vartex n = edge.linked;
int dist = peek.dist + edge.weight;
if (dist < n.dist)
n.dist = dist;
n.prev = peek;
}
peek.visited=true;
}
//3.当前结点出队
vartex poll= queue.poll();
}
for(vartex v:graph){
System.out.println(v.name+" "+v.dist+" "+(v.prev!=null?v.prev.name:null));
}
}
}二.贝尔曼福特算法
贝尔曼福特算法,单源最短路径可以处理负边 循环顶点次数减一次,遍历每个顶点的每条边，更新与邻居之间的距离 贝尔曼，有负环出现，检测负环只需要看循环顶点个数减一次后是否再次进入if
package LanQiao.MinDist;
import java.util.List;
//贝尔曼福特算法,单源最短路径
// 可以处理负边
//循环顶点次数减一次,遍历每个顶点每条边，更新距离
//贝尔曼，有负环出现，检测负环只需要看循环顶点个数减一次后是否再次进入if
public class BellmanFord {
public static class vartex {
String name;
List<Edge> edges;
int dist = INF;
static final Integer INF = Integer.MAX_VALUE;
boolean visited;
vartex prev=null;
public vartex(String name) {
this.name = name;
}
}
static class Edge {
public Edge(vartex linked, int weight) {
this.linked = linked;
this.weight = weight;
}
vartex linked;
int weight;
}
public static void main(String[] args) {
vartex v1 = new vartex("v1");
vartex v2 = new vartex("v2");
vartex v3 = new vartex("v3");
vartex v4 = new vartex("v4");
v1.edges = List.of(new Edge(v2, 2), new Edge(v3, 1));
v2.edges = List.of(new Edge(v3, -2));
v3.edges = List.of(new Edge(v4, 1));
v4.edges = List.of();
List<vartex> graph = List.of(v1, v2, v3, v4);
bellmanFoed(graph, v1);
}
private static void bellmanFoed(List<vartex> graph, vartex v1) {
v1.dist = 0;
for (int i = 0; i < graph.size() - 1; i++) {
for (vartex s : graph) {//遍历每个顶点每条边
for (Edge edge : s.edges) {//设置边的起点终点
vartex e = edge.linked;
if (s.dist != Integer.MAX_VALUE && edge.weight + s.dist < e.dist) {//注意条件
e.dist = edge.weight + s.dist;
e.prev=s;
}
}
}
}
for (vartex v:graph){
System.out.println(v.name+" "+v.dist+" "+(v.prev!=null?v.prev.name:null));
}
}
}
三.弗洛伊德算法
FloydWarShall求多源最短路径长度
创建距离矩阵
3重循环
通过v1,v2,v3,v4借路到其他顶点，
j到i到距离加上i到k的距离等于j到k的距离先写大变是最里层，遍历中间节点那一行元素，纵坐标
小变是中间节点（借路的那个节点），最外层/可处理负边，不能处理负环
判断负环，需要每次判断对角线是否出现负数（正常情况下对角线都是0）
package LanQiao.MinDist;
import java.util.Collection;
import java.util.List;
import java.util.Map;
import java.util.stream.Collector;
import java.util.stream.Collectors;
public class FloydWarShall {
//FloydWarShall求多源最短路径长度
//创建距离矩阵
// 3重循环
//通过v1,v2,v3,v4借路到其他顶点，
//j到i到距离加上i到k的距离等于j到k的距离
//先写大变是最里层，遍历中间节点那一行元素，纵坐标
// 小变是中间节点（借路的那个节点），最外层
// 可处理负边，不能处理负环
//判断负环，需要每次判断对角线是否出现负数（正常情况下对角线都是0）
public static class vartex {
String name;
List<Edge> edges;
int dist = INF;
static final Integer INF = Integer.MAX_VALUE;
boolean visited;
public vartex(String name) {
this.name = name;
}
}
static class Edge {
public Edge(vartex linked, int weight) {
this.linked = linked;
this.weight = weight;
}
vartex linked;
int weight;
}
public static void main(String[] args) {
vartex v1 = new vartex("v1");
vartex v2 = new vartex("v2");
vartex v3 = new vartex("v3");
vartex v4 = new vartex("v4");
v1.edges = List.of(new Edge(v3, -2));
v2.edges = List.of(new Edge(v1, 4), new Edge(v3, 3));
v3.edges = List.of(new Edge(v4, 2));
v4.edges = List.of(new Edge(v2, -1));
List<vartex> graph = List.of(v1, v2, v3, v4);
floydWarShall(graph);
}
private static void floydWarShall(List<vartex> graph) {
int n = graph.size();
vartex prev[][]=new vartex[n][n];
int[][] dist = new int[n][n];//创建距离矩阵
for (int i = 0; i < n; i++) {
vartex v = graph.get(i);
Map<vartex, Integer> map = v.edges.stream().collect(Collectors.toMap(e -> e.linked, e -> e.weight));
for (int j = 0; j < n; j++) {
vartex u = graph.get(j);
if (v == u) {
dist[i][j] = 0;//元素相同距离为0
} else {
//从v的Linked找到u,若成功返回对应的weight,若失败返回最大值
dist[i][j] = map.getOrDefault(u, Integer.MAX_VALUE);
// prev[i][j]=map.get(j);
}
}
}
print(dist);
//核心思想借路到其他顶点
for (int i = 0; i < dist.length; i++) {
for (int j = 0; j < dist.length; j++) {
for (int k = 0; k < dist.length; k++) {
if (dist[j][i] != Integer.MAX_VALUE && dist[i][k] != Integer.MAX_VALUE && dist[j][i] + dist[i][k] < dist[j][k]) {
dist[j][k] = dist[j][i] + dist[i][k];
}
//通过v1,v2,v3,v4借路到其他顶点，
//j到i到距离加上i到k的距离等于j到k的距离
// 3重循环
//先写大变是最里层，遍历中间节点那一行元素，纵坐标
// 小变是中间节点（借路的那个节点），最外层
}
}
print(dist);
System.out.println();
}
}
private static void print(int[][] dist) {
for (int i = 0; i < dist.length; i++) {
for (int j = 0; j < dist.length; j++) {
if (dist[i][j] == Integer.MAX_VALUE) {
System.out.print("&" + " ");
} else {
System.out.print(dist[i][j] + " ");
}
}
System.out.println();
}
}
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
5
0- 0
已为社区贡献2条内容
所有评论(0)