dijkstra算法-非负权值求最短路
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int[][] grid = new int[n + 1][n + 1]; for (int i = 0; i <= n; i++) { Arrays.fill(grid[i], Integer.MAX_VALUE); } for (int i = 0; i < m; i++) { int p1 = scanner.nextInt(); int p2 = scanner.nextInt(); int val = scanner.nextInt(); grid[p1][p2] = val; } int start = 1; int end = n; // 存储从源点到每个节点的最短距离 int[] minDist = new int[n + 1]; Arrays.fill(minDist, Integer.MAX_VALUE); // 记录顶点是否被访问过 boolean[] visited = new boolean[n + 1]; minDist[start] = 0; // 起始点到自身的距离为0 for (int i = 1; i <= n; i++) { // 遍历所有节点 int minVal = Integer.MAX_VALUE; int cur = 1; // 1、选距离源点最近且未访问过的节点 for (int v = 1; v <= n; ++v) { if (!visited[v] && minDist[v] < minVal) { minVal = minDist[v]; cur = v; } } visited[cur] = true; // 2、标记该节点已被访问 // 3、第三步，更新非访问节点到源点的距离（即更新minDist数组） for (int v = 1; v <= n; v++) { if (!visited[v] && grid[cur][v] != Integer.MAX_VALUE && minDist[cur] + grid[cur][v] < minDist[v]) { minDist[v] = minDist[cur] + grid[cur][v]; } } } if (minDist[end] == Integer.MAX_VALUE) { System.out.println(-1); // 不能到达终点 } else { System.out.println(minDist[end]); // 到达终点最短路径 } } }假如有n个节点，要找出到达目的节点经过n-1条路径，需要松弛n-1次。
松弛过程如下：要从1到4，三条边
第一次松弛
其他节点对应的minDist初始化为max，因为我们要求最小距离，那么还没有计算过的节点 默认是一个最大数，这样才能更新最小距离。
当我们开始对所有边开始第一次松弛：
边：节点1 -> 节点2，权值为-1 ，minDist[2] > minDist[1] + (-1)，更新 minDist[2] = minDist[1] + (-1) = 0 - 1 = -1 ，如图：
边：节点2 -> 节点3，权值为1 ，minDist[3] > minDist[2] + 1 ，更新 minDist[3] = minDist[2] + 1 = -1 + 1 = 0 ，如图：
边：节点3 -> 节点1，权值为-1 ，minDist[1] > minDist[3] + (-1)，更新 minDist[1] = 0 + (-1) = -1 ，如图：
边：节点3 -> 节点4，权值为1 ，minDist[4] > minDist[3] + 1，更新 minDist[4] = 0 + 1 = 1 ，如图：
以上是对所有边进行的第一次松弛，最后 minDist数组为 ：-1 -1 0 1 ，（从下标1算起）
所有边进行的第二次松弛，minDist数组为 ： -2 -2 -1 0 所有边进行的第三次松弛，minDist数组为 ： -3 -3 -2 -1 所有边进行的第四次松弛，minDist数组为 ： -4 -4 -3 -2 （本示例中k为3，所以松弛4次）
最后计算的结果minDist[4] = -2，即 起点到 节点4，最多经过 3 个节点的最短距离是 -2，但 正确的结果应该是 1，即路径：节点1 -> 节点2 -> 节点3 -> 节点4。
理论上来说，对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。
对所有边松弛两次，相当于计算 起点到达 与起点两条边相连的节点的最短距离。
对路径权重进行排序后的松弛
边：节点3 -> 节点1，权值为-1 ，节点3还没有被计算过，节点1 不更新。
边：节点3 -> 节点4，权值为1 ，节点3还没有被计算过，节点4 不更新。
边：节点2 -> 节点3，权值为 1 ，节点2还没有被计算过，节点3 不更新。
边：节点1 -> 节点2，权值为 -1 ，minDist[2] > minDist[1] + (-1)，更新 minDist[2] = 0 + (-1) = -1 ，如图：
基于负权值的最优路径
简单单源有向图-Bellman_ford
import java.util.*; public class Main { // 基于Bellman_for一般解法解决单源最短路径问题 // Define an inner class Edge static class Edge { int from; int to; int val; public Edge(int from, int to, int val) { this.from = from; this.to = to; this.val = val; } } public static void main(String[] args) { // Input processing Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); List<Edge> graph = new ArrayList<>(); for (int i = 0; i < m; i++) { int from = sc.nextInt(); int to = sc.nextInt(); int val = sc.nextInt(); graph.add(new Edge(from, to, val)); } int src = sc.nextInt(); int dst = sc.nextInt(); int k = sc.nextInt(); int[] minDist = new int[n + 1]; int[] minDistCopy; Arrays.fill(minDist, Integer.MAX_VALUE); minDist[src] = 0; for (int i = 0; i < k + 1; i++) { // Relax all edges k + 1 times minDistCopy = Arrays.copyOf(minDist, n + 1); for (Edge edge : graph) { int from = edge.from; int to = edge.to; int val = edge.val; // Use minDistCopy to calculate minDist if (minDistCopy[from] != Integer.MAX_VALUE && minDist[to] > minDistCopy[from] + val) { minDist[to] = minDistCopy[from] + val; } } } // Output printing if (minDist[dst] == Integer.MAX_VALUE) { System.out.println("unreachable"); } else { System.out.println(minDist[dst]); } } }含有负权回路的最短路径-SPFA
class Edge { public int u; // 边的端点1 public int v; // 边的端点2 public int val; // 边的权值 public Edge() { } public Edge(int u, int v) { this.u = u; this.v = v; this.val = 0; } public Edge(int u, int v, int val) { this.u = u; this.v = v; this.val = val; } } /** * SPFA算法（版本3）：处理含【负权回路】的有向图的最短路径问题 * bellman_ford（版本3） 的队列优化算法版本 * 限定起点、终点、至多途径k个节点 */ public class SPFAForSSSP { /** * SPFA算法 * * @param n 节点个数[1,n] * @param graph 邻接表 * @param startIdx 开始节点（源点） */ public static int[] spfa(int n, List<List<Edge>> graph, int startIdx, int k) { // 定义最大范围 int maxVal = Integer.MAX_VALUE; // minDist[i] 源点到节点i的最短距离 int[] minDist = new int[n + 1]; // 有效节点编号范围：[1,n] Arrays.fill(minDist, maxVal); // 初始化为maxVal minDist[startIdx] = 0; // 设置源点到源点的最短路径为0 // 定义queue记录每一次松弛更新的节点 Queue<Integer> queue = new LinkedList<>(); queue.offer(startIdx); // 初始化：源点开始（queue和minDist的更新是同步的） // SPFA算法核心：只对上一次松弛的时候更新过的节点关联的边进行松弛操作 while (k + 1 > 0 && !queue.isEmpty()) { // 限定松弛 k+1 次 int curSize = queue.size(); // 记录当前队列节点个数（上一次松弛更新的节点个数，用作分层统计） while (curSize-- > 0) { //分层控制，限定本次松弛只针对上一次松弛更新的节点，不对新增的节点做处理 // 记录当前minDist状态，作为本次松弛的基础 int[] minDist_copy = Arrays.copyOfRange(minDist, 0, minDist.length); // 取出节点 int cur = queue.poll(); // 获取cur节点关联的边，进行松弛操作 List<Edge> relateEdges = graph.get(cur); for (Edge edge : relateEdges) { int u = edge.u; // 与`cur`对照 int v = edge.v; int weight = edge.val; if (minDist_copy[u] + weight < minDist[v]) { minDist[v] = minDist_copy[u] + weight; // 更新 // 队列同步更新（此处有一个针对队列的优化:就是如果已经存在于队列的元素不需要重复添加） if (!queue.contains(v)) { queue.offer(v); // 与minDist[i]同步更新，将本次更新的节点加入队列，用做下一个松弛的参考基础 } } } } // 当次松弛结束，次数-1 k--; } // 返回minDist return minDist; } public static void main(String[] args) { // 输入控制 Scanner sc = new Scanner(System.in); System.out.println("1.输入N个节点、M条边（u v weight）"); int n = sc.nextInt(); int m = sc.nextInt(); System.out.println("2.输入M条边"); List<List<Edge>> graph = new ArrayList<>(); // 构建邻接表 for (int i = 0; i <= n; i++) { graph.add(new ArrayList<>()); } while (m-- > 0) { int u = sc.nextInt(); int v = sc.nextInt(); int weight = sc.nextInt(); graph.get(u).add(new Edge(u, v, weight)); } System.out.println("3.输入src dst k（起点、终点、至多途径k个点）"); int src = sc.nextInt(); int dst = sc.nextInt(); int k = sc.nextInt(); // 调用算法 int[] minDist = SPFAForSSSP.spfa(n, graph, src, k); // 校验起点->终点 if (minDist[dst] == Integer.MAX_VALUE) { System.out.println("unreachable"); } else { System.out.println("最短路径：" + minDist[n]); } } }双向相同权值多个源节点的目的节点-Floyd算法
public class FloydBase { // public static int MAX_VAL = Integer.MAX_VALUE; public static int MAX_VAL = 10005; // 边的最大距离是10^4(不选用Integer.MAX_VALUE是为了避免相加导致数值溢出) public static void main(String[] args) { // 输入控制 Scanner sc = new Scanner(System.in); System.out.println("1.输入N M"); int n = sc.nextInt(); int m = sc.nextInt(); System.out.println("2.输入M条边"); // ① dp定义（grid[i][j][k] 节点i到节点j 可能经过节点K（k∈[1,n]））的最短路径 int[][][] grid = new int[n + 1][n + 1][n + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 0; k <= n; k++) { grid[i][j][k] = grid[j][i][k] = MAX_VAL; // 其余设置为最大值 } } } // ② dp 推导：grid[i][j][k] = min{grid[i][k][k-1] + grid[k][j][k-1], grid[i][j][k-1]} while (m-- > 0) { int u = sc.nextInt(); int v = sc.nextInt(); int weight = sc.nextInt(); grid[u][v][0] = grid[v][u][0] = weight; // 初始化（处理k=0的情况） ③ dp初始化 } // ④ dp推导：floyd 推导 for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { grid[i][j][k] = Math.min(grid[i][k][k - 1] + grid[k][j][k - 1], grid[i][j][k - 1]); } } } System.out.println("3.输入[起点-终点]计划个数"); int x = sc.nextInt(); System.out.println("4.输入每个起点src 终点dst"); while (x-- > 0) { int src = sc.nextInt(); int dst = sc.nextInt(); // 根据floyd推导结果输出计划路径的最小距离 if (grid[src][dst][n] == MAX_VAL) { System.out.println("-1"); } else { System.out.println(grid[src][dst][n]); } } } }
