最短路问题之Bellman-ford算法
2024-10-19 04:22:07
题目：
最短路：给定两个顶点，在以这两个点为起点和终点的路径中，边的权值和最小的路径。考虑权值为点之间的距离。
单源最短路问题，Bellman-ford算法
思路：每次循环检查所有边，可优化。
应用于旅游等路径最小问题。
代码：
import java.util.Arrays;
public class 图的最短路问题_单源 {
public static void main(String[] args) {
int[] shortestPath = shortestPath(0);
System.out.println(Arrays.toString(shortestPath));
// 输出[0, 2, 5, 7, 11, 8, 16]
}
/**
* 求起点到各顶点的最短距离
*
* @param s 起点
* @return
*/
private static int[] shortestPath(int s) {
int n = graph.length;
// 记录s到各顶点的最短距离
int[] d = new int[n];
for (int i = 0; i < n; i++) {
d[i] = Integer.MAX_VALUE;
}
d[s] = 0;// 到自己的距离为0
while (true) {
boolean update = false;
// 扫描所有的边
for (int i = 0; i < n; i++) {
// 起点到i的最短距离还没算出来
if (d[i] == Integer.MAX_VALUE)
continue;
for (int j = 0; j < n; j++) {
int cost = graph[i][j]; // i,j之间的距离
if (cost > 0) { // i,j 两点之间有边，起点是i
if (d[j] > d[i] + cost) { // 起点先到i，i->j
// 两端距离加起来比起点直接到j的距离短，则更新
update = true;
d[j] = d[i] + cost;
}
}
}
}
// 无需任何更新，退出外循环
if (!update)
break;
}
return d;
}
static int[][] graph = {
{ 0, 2, 5, 0, 0, 0, 0 },
{ 2, 0, 4, 6, 10, 0, 0 },
{ 5, 4, 0, 2, 0, 0, 0 },
{ 0, 6, 2, 0, 0, 1, 0 },
{ 0, 10, 0, 0, 0, 3, 5 },
{ 0, 0, 0, 1, 3, 0, 9 },
{ 0, 0, 0, 0, 5, 9, 0 }
};
}
对于上一个代码。可以先把边集提取出来，这样不用每次扫描二维数组。
Edge类：
/**
* 边 的封装
* 边集可以用来表示图
*/
public class Edge<T> implements Comparable<Edge> {
private T start;
private T end;
private int distance; public Edge(T start, T end, int distance) {
this.start = start;
this.end = end;
this.distance = distance;
} public T getStart() {
return start;
} public void setStart(T start) {
this.start = start;
} public T getEnd() {
return end;
} public void setEnd(T end) {
this.end = end;
} public int getDistance() {
return distance;
} public void setDistance(int distance) {
this.distance = distance;
} @Override
public String toString() {
return start + "->" + end + ":" + distance;
} @Override
public int compareTo(Edge obj) {
int targetDis = obj.getDistance();
return distance > targetDis ? 1 : (distance == targetDis ? 0 : -1);
}
}
优化过后的代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List; public class 图的最短路问题_优化_边集 {
public static void main(String[] args) {
edges = buildEdges(graph);
int[] shortestPath = shortestPath(0);
System.out.println(Arrays.toString(shortestPath));
// 输出[0, 2, 5, 7, 11, 8, 16]
} /**
* 求起点到各顶点的最短距离
*
* @param s
* 起点
* @return
*/
private static int[] shortestPath(int s) {
int n = graph.length;
// 记录s到各顶点的最短距离
int[] d = new int[n];
for (int i = 0; i < n; i++) {
d[i] = Integer.MAX_VALUE;
}
d[s] = 0;// 到自己的距离为0
while (true) {
boolean update = false; for (Edge<Integer> e : edges) {
if (d[e.getStart()] != Integer.MAX_VALUE && d[e.getEnd()] > d[e.getStart()] + e.getDistance()) {
update = true;
d[e.getEnd()] = d[e.getStart()] + e.getDistance();
}
} if (!update)
break;
}
return d;
} static List<Edge<Integer>> edges; static List<Edge<Integer>> buildEdges(int[][] graph) {
int n = graph.length;
List<Edge<Integer>> edges = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int cost = graph[i][j]; // i,j之间的距离
if (cost > 0) { // i,j 两点之间有边，起点是i
edges.add(new Edge<>(i, j, cost));
}
}
}
return edges;
} static int[][] graph = {
{ 0, 2, 5, 0, 0, 0, 0 },
{ 2, 0, 4, 6, 10, 0, 0 },
{ 5, 4, 0, 2, 0, 0, 0 },
{ 0, 6, 2, 0, 0, 1, 0 },
{ 0, 10, 0, 0, 0, 3, 5 },
{ 0, 0, 0, 1, 3, 0, 9 },
{ 0, 0, 0, 0, 5, 9, 0 }
};
}
最新文章
- linux中inode、软链接、硬链接
- tornado 学习笔记5 构建Tornado网站应用
- java 的SYSTEM类【转】
- golang处理错误的艺术
- POJ 2226 Muddy Fields (最小点覆盖集，对比POJ 3041)
- Hadoop学习总结之五：Hadoop的运行痕迹
- Part 92 Significance of Thread Join and Thread IsAlive functions
- oracle 日志学习（转载）
- 流形（Manifold）初步【转】
- show_space.sql.txt
- PAT乙级练习1001
- UIEvent&nbsp;UIResponder&nbsp;UI_04
- Maven入门教程（一）
- 转导推理——Transductive Learning
- Django-rest-framework 接口实现 认证:(auth | authentication)
- （转载）C#使用MemoryStream类读写内存
- Java中Access restriction：····的解决方法
- Python 语法糖装饰器的应用
- 启动项目报错：502 Server dropped connection The following error occurred while trying to access http://localhost:8080/TestDemo:
- （译）我为什么用Go语言来做区块链——Syed Jafar Naqvi——Co-Founder/CEO at Karachain