邻接矩阵&＃xff1a;适用于边数较多的稠密图使用&＃xff0c;
邻接表&＃xff1a;适用于边数较少的稀疏图使用&＃xff0c;当边数量接近点的数量&＃xff0c; m&＃61;n
类:
class Edge {
int start, end, weight;
Edge(int _a, int _b, int _c) {
start &＃61; _a;
end &＃61; _b;
weight &＃61; _c;
}
}
2.1 朴素版
/** 2.2 堆优化版 通过堆替代 所有边找最短结点 /** /** 理解 Bellman-ford算法_bellmanford算法_十七溯的博客-CSDN博客 防止串联原理 Bellman-ford算法详解_bellmanford算法_真的没事鸭的博客-CSDN博客 核心代码 //经过 n - 1次松驰 5.1 SPFA求最短路径 SPFA算法&＃xff08;最短路径算法&＃xff09;_钟一淼的博客-CSDN博客 1.用dis数组记录点到有向图的任意一点距离&＃xff0c;初始化起点距离为0&＃xff0c;其余点均为INF&＃xff0c;起点入队。 2.判断该点是否存在。&＃xff08;未存在就入队&＃xff0c;标记&＃xff09; 3.队首出队&＃xff0c;并将该点标记为没有访问过&＃xff0c;方便下次入队。 4.遍历以对首为起点的有向边&＃xff08;t,i&＃xff09;,如果dis[i]>dis[t]&＃43;w(t,i),则更新dis[i]。 5.如果i不在队列中&＃xff0c;则入队标记&＃xff0c;一直到循环为空。 /** 5.2 SPFA求负环 852. spfa判断负环_51CTO博客_spfa判断负环 负环&＃xff0c;又叫负权回路&＃xff0c;负权环&＃xff0c;指的是一个图中存在一个环&＃xff0c;里面包含的边的边权总和<0 &＃xff08;1&＃xff09;(spfa)可以用来判断是不是有向图中存在负环。 &＃xff08;2&＃xff09;基本原理&＃xff1a;利用抽屉原理 基于抽屉原理&＃xff0c;如果一条正在搜索的最短路径上的点的个数大于总共点的个数&＃xff0c;则说明路径上一定有至少重复的两个点&＃xff0c;走了回头路。 (dist[x])的概念是指当前从(1)号点到(x)号点的最短路径的长度。(dist[x]&＃61;dist[t]&＃43;w[i]) (cnt[x])的概念是指当前从(1)号点到(x)号点的最短路径的边数量。(cnt[x]&＃61;cnt[t]&＃43;1) 如果发现(cnt[x]>&＃61;n),就意味着从(1&＃xff09;&＃xff08;x)经历了(n)条边&＃xff0c;那么必须经过了(n&＃43;1)个点&＃xff0c;但问题是点一共只有(n)个&＃xff0c;所以必然有两个点是相同的&＃xff0c;就是有一个环。 因为是在不断求最短路径的过程中发现了环&＃xff0c;路径长度在不断变小的情况下发现了环&＃xff0c;那么&＃xff0c;只能是负环。 (1)号点是源节点的意思 &＃xff08;3&＃xff09;为什么初始化时初始值为(0),而且把所有结点都加入队列&＃xff1f; 在原图的基础上新建一个虚拟源点&＃xff0c;从该点向其他所有点连一条权值为(0)的有向边。那么原图有负环等价于新图有负环。此时在新图上做(spfa)&＃xff0c;将虚拟源点加入队列中。然后进行(spfa)的第一次迭代&＃xff0c;这时会将所有点的距离更新并将所有点插入队列中。执行到这一步&＃xff0c;就等价于下面代码中的做法了。如果新图有负环&＃xff0c;等价于原图有负环。 /**
* 贪心 O N^2
* 1.找距离最短的节点 2.计算该节点扩展的边
*
* 源节点加入最短路径集合&＃xff0c;先算出这个节点的周围路径长度。 继续加入 不属于这个集合的且到这个集合 路径最短的节点&＃xff0c;再算边
* 注意&＃xff1a;graph是根据下标两点之间的值&＃xff0c;如果到达不了则设置为Integer.MAXVALUE&＃xff0c;不一定是lc题目那种
*
* P743网络延迟时间 https://leetcode.cn/problems/network-delay-time/solution/gong-shui-san-xie-yi-ti-wu-jie-wu-chong-oghpz/
* 存图方式
* 在开始讲解最短路之前&＃xff0c;我们先来学习三种「存图」方式。
*
* 邻接矩阵
* 这是一种使用二维矩阵来进行存图的方式。
*
* 适用于边数较多的稠密图使用&＃xff0c;当边数量接近点的数量的平方
*/
public class Dijkstra {
public int[] dijkstra(int[][] graph, int n, int k) {
int INF &＃61; Integer.MAX_VALUE;
// 源节点到其他节点的最短距离
int[] dist &＃61; new int[n];
Arrays.fill(dist, INF);
// 源节点到自身距离为0
dist[k] &＃61; 0;
// 最短路径节点集合
boolean[] visited &＃61; new boolean[n];
// 1.找距离最短的节点 2.计算该节点扩展的边
// n -1 也行&＃xff0c;是最后一轮循环确定倒数第二个节点时&＃xff0c;也确定了到最后一个节点的边距离&＃xff0c;可以省一轮遍历
for (int i &＃61; 0; i
// 源节点无法到达任务一个点
if (x &＃61;&＃61; -1) {
return dist;
}
visited[x] &＃61; true;
for (int y &＃61; 0; y
if (graph[x][y] !&＃61; Integer.MAX_VALUE && dist[x] &＃43; graph[x][y]
}
}
}
return dist;
}
// 首次默认是源节点&＃xff0c;找到距离最短的节点 这里是遍历所有的点到该点距离
private int findNextNode(int[] dist, boolean[] visit, int n) {
int u &＃61; -1;
int min &＃61; Integer.MAX_VALUE;
for (int j &＃61; 0; j
u &＃61; j;
}
}
return u;
}
// 下面也可以这样找最短节点 代替 findNextNode()&＃xff0c;但是不通的节点也会加入计算&＃xff0c;多余了点步骤
// int x &＃61; -1;
// for (int y &＃61; 0; y
// }
// }
}
* 堆优化 - Dijkstra O(mlogn&＃43;n)
* 邻接表&＃xff08;数组&＃xff09;
* 这也是一种在图论中十分常见的存图方式&＃xff0c;与数组存储单链表的实现一致&＃xff08;头插法&＃xff09;。
*
* 这种存图方式又叫链式前向星存图。
*
* 适用于边数较少的稀疏图使用&＃xff0c;当边数量接近点的数量&＃xff0c; m&＃61;n
* 下标0开始
*/
public class DijistraHeapMy {
// 头节点指向的边
private int[] srcToEdge;
// 边指向节点
private int[] edgeToDist;
// 边的下一条边&＃xff0c;同一个出发节点src 简称邻接边
private int[] nextEdge;
// 边的权重
private int[] w;
private int[] dist;
private boolean[] visited;
private int idx;
private int INF &＃61; Integer.MAX_VALUE;
private void add(int srcV, int distV, int weight) {
this.edgeToDist[idx] &＃61; distV;
this.nextEdge[idx] &＃61; this.srcToEdge[srcV];
this.srcToEdge[srcV] &＃61; idx;
this.w[idx] &＃61; weight;
idx&＃43;&＃43;;
}
private void init(int n) {
visited &＃61; new boolean[n];
dist &＃61; new int[n];
w &＃61; new int[6000];
nextEdge &＃61; new int[6000]; // 题目要求的边最多6000
srcToEdge &＃61; new int[n]; // 头节点数量
edgeToDist &＃61; new int[6000];
Arrays.fill(srcToEdge, -1);
Arrays.fill(nextEdge, -1);
Arrays.fill(edgeToDist, -1);
Arrays.fill(dist, INF);
Arrays.fill(visited, false);
}
// k:源节点的下标&＃xff0c;从0开始
public int[] dijkstra(int[][] times, int n, int k) {
// 初始化数组
init(n);
for (int[] ts : times) {
// 从下标0开始
add(ts[0] - 1, ts[1] - 1, ts[2]);
}
PriorityQueue
queue.add(new int[]{k, 0});
dist[k] &＃61; 0;
while (!queue.isEmpty()) {
// 确定点
int v &＃61; queue.poll()[0];
if (visited[v]) {
continue;
}
visited[v] &＃61; true;
// 确定最短集合边
for (int i &＃61; srcToEdge[v]; i !&＃61; -1; i &＃61; nextEdge[i]) {
int distNode &＃61; edgeToDist[i];
System.out.println("结点" &＃43; v &＃43; " -> 结点" &＃43; distNode);
System.out.println("编号为" &＃43; idx &＃43; "的边, 权重为: " &＃43; w[idx]);
// 由于是通过边数组确定的&＃xff0c;所以这里不用判断 !&＃61;INF 因为都是能通的边
if (w[i] &＃43; dist[v]
queue.add(new int[]{distNode, dist[distNode]});
}
}
}
return dist;
}
} 3. Floyd算法
* 动态规划 - 邻接矩阵 O N^3
*
* 跑一遍 Floyd&＃xff0c;可以得到「从任意起点出发&＃xff0c;到达任意起点的最短距离 时间复杂度On 3 > Dijkstra On 2
*
* P743网络延迟时间Floyd
*
* 通过循环每个中转点求路径
*/
public class Floyd {
private static int INF &＃61; Integer.MAX_VALUE;
/**
* 距离矩阵 自身为0&＃xff0c;到达不了为INF
*/
public static int[][] distance;
/**
* 路径矩阵
*/
public static int[][] path; // 一些求最短距离的点不需要记录路径矩阵也行
public static void floyd(int[][] graph) {
//初始化距离矩阵 distance
distance &＃61; graph;
//初始化路径
path &＃61; new int[graph.length][graph.length];
for (int i &＃61; 0; i
}
}
//开始 Floyd 算法
//每个点为中转
for (int i &＃61; 0; i
for (int j &＃61; 0; j
for (int k &＃61; 0; k
//例如 AB &＃43; BC
// 如果两点到达不了也只能是 走中转节点
if (graph[j][i] &＃43; graph[i][k]
graph[j][k] &＃61; graph[j][i] &＃43; graph[i][k];
//刷新路径
path[j][k] &＃61; i;
}
}
}
}
}
}
/**
* 测试
*/
public static void main(String[] args) {
// int[][] graph &＃61; new int[][]{
// {0, 2, INF, 6}
// , {2, 0, 3, 2}
// , {INF, 3, 0, 2}
// , {6, 2, 2, 0}};
// 以下是转换后的 graph
int[][] graph &＃61; new int[][]{
{0, 1, INF, INF}
, {INF, 0, 1, INF}
, {INF, INF, 0, 1}
, {INF, INF, INF, 0}};
floyd(graph);
System.out.println("&＃61;&＃61;&＃61;&＃61;distance&＃61;&＃61;&＃61;&＃61;");
// distance根据graph 修改为最短路径数组
for (int[] ints : distance) {
for (int anInt : ints) {
System.out.print(anInt &＃43; " ");
}
System.out.println();
}
System.out.println("&＃61;&＃61;&＃61;&＃61;path&＃61;&＃61;&＃61;&＃61;");
for (int[] ints : path) {
for (int anInt : ints) {
System.out.print(anInt &＃43; " ");
}
System.out.println();
}
}
} 4. Bellman-ford算法
//对所有边进行一次松弛操作&＃xff0c;就求出了源点到所有点&＃xff0c;经过的边数最多为1的最短路
//对所有边进行两次松弛操作&＃xff0c;就求出了源点到所有点&＃xff0c;经过的边数最多为2的最短路
//....
//对所有边进行n- 1次松弛操作&＃xff0c;就求出了源点到所有点&＃xff0c;经过的边数最多为n - 1的最短路
for(int i &＃61; 0; i
//遍历所有边
for(int j &＃61; 0; j
if(dis[a] !&＃61; 0x3f3f3f3f && dis[b] > dis[a] &＃43; w) //松弛操作
dis[b] &＃61; dis[a] &＃43; w;
}
} 5. SPFA算法
* 对 BellmanFord 的优化 求最短路径 O M*N
* 能够解决负环问题&＃xff1a; 负环&＃xff0c;又叫负权回路&＃xff0c;负权环&＃xff0c;指的是一个图中存在一个环&＃xff0c;里面包含的边的边权总和<0
*
* 与Dikstra类似&＃xff0c;D是类似DFS找最短距离的点深入&＃xff0c;SPFA是类似BFS每次从相邻节点扩展&＃xff0c;而且访问过可以重复访问&＃xff0c;可以解决负环问题
*
* https://blog.csdn.net/m0_64045085/article/details/123547253
*/
public class SpfaMy {
// 边到节点
private int[] edgeToNode;
// 邻接边
private int[] nextEdge;
// 结点到边
private int[] srcToEdge;
// 边权重
private int[] w;
// 第几条边,从0开始
private int idx;
private boolean[] visited;
private int INF &＃61; Integer.MAX_VALUE;
// 这里 k times 从下标1开始
public int[] spfa(int[][] times, int n, int k) {
// 初始化最短距离
int[] dist &＃61; new int[n &＃43; 1];
Arrays.fill(dist, INF);
dist[k] &＃61; 0;
// 初始化是否访问过 由于下表从1开始所以n&＃43;1
visited &＃61; new boolean[n &＃43; 1];
Arrays.fill(visited, false);
visited[k] &＃61; true;
// 初始化表
edgeToNode &＃61; new int[6000]; // 题目最多6000条边
nextEdge &＃61; new int[6000];
srcToEdge &＃61; new int[n &＃43; 1]; // 由于下表从1开始所以n&＃43;1
w &＃61; new int[6000];
// 初始化邻接表
Arrays.fill(srcToEdge, -1);
Arrays.fill(nextEdge, -1);
for (int[] ts : times) {
edgeToNode[idx] &＃61; ts[1];
nextEdge[idx] &＃61; srcToEdge[ts[0]];
srcToEdge[ts[0]] &＃61; idx;
w[idx] &＃61; ts[2];
idx&＃43;&＃43;;
}
// 初始化队列
Deque
queue.add(k);
while (!queue.isEmpty()) {
System.out.print("队列此时为" &＃43; queue);
Integer poll &＃61; queue.poll();
visited[poll] &＃61; false; // 这是能够探测负权的操作&＃xff0c;如果原结点的距离更短&＃xff0c;则最短路径继续能探测原结点
System.out.println("&＃xff0c;更新" &＃43; poll &＃43; "结点");
// 循环点的邻接边 i是边 j是结点
for (int i &＃61; srcToEdge[poll]; i !&＃61; -1; i &＃61; nextEdge[i]) {
int j &＃61; edgeToNode[i];
if (dist[poll] &＃43; w[i]
System.out.println("计算 " &＃43; poll &＃43; " 至 " &＃43; j &＃43; " &＃xff0c;到 " &＃43; j &＃43; " 最短距离为 " &＃43; dist[j]);
if (!visited[j]) {
queue.add(j);
visited[j] &＃61; true;
}
}
}
}
return dist;
}
}
* 对 BellmanFord 的优化 判断负环 O M*N
* 能够解决负环问题&＃xff1a; 负环&＃xff0c;又叫负权回路&＃xff0c;负权环&＃xff0c;指的是一个图中存在一个环&＃xff0c;里面包含的边的边权总和<0
* https://blog.51cto.com/u_3044148/4028313
*
* 抽屉原理&＃xff0c;如果一条正在搜索的[最短路径]上的点的个数大于总共点的个数&＃xff0c;则说明路径上一定有至少重复的两个点&＃xff0c;走了回头路
* 某个点的入队数大于了n&＃xff0c;证明他在不停得松弛
*/
public class SpfaMyNegativeRing {
class Edge {
private int start;
private int end;
private int w;
public Edge(int a, int b, int c) {
this.start &＃61; a;
this.end &＃61; b;
this.w &＃61; c;
}
}
private List
// 这里times 从下标0开始
public boolean spfa(int[][] times, int n) {
// 初始化队列
Deque
for (int i &＃61; 0; i
// 每个点都相当于虚拟源点&＃xff0c;只要从这个点出发的最短路径上&＃xff0c;某个点入队超过N&＃xff0c;就是有负环
queue.add(i);
}
for (int[] ts : times) {
es.add(new Edge(ts[0] - 1, ts[1] - 1, ts[2]));
}
// 都设置为0&＃xff0c;只有负数的情况下才会是最短路径,没有负数就没有负环
int[] dist &＃61; new int[n];
// 源点到下标点的最短路径的边数量
int[] cnt &＃61; new int[n];
boolean[] visited &＃61; new boolean[n];
while (!queue.isEmpty()) {
int poll &＃61; queue.poll();
visited[poll] &＃61; false;
// 此处不是邻接边&＃xff0c;是所有边了
for (Edge edge : es) {
// 由于所有的最短路径 dist都是0&＃xff0c;所以只有负数的才会是最短路径
if (dist[poll] &＃43; edge.w
// 到达的点入队的数标为前面这个点入队的次数&＃43;1 , 假设循环是好几个点负边连起来的就明白了&＃xff0c; 1->2->3>1 权值都为负数
cnt[edge.end] &＃61; cnt[poll] &＃43; 1;
if (cnt[edge.end] >&＃61; n) {
return false;
}
if (!visited[edge.end]) {
queue.add(edge.end);
visited[edge.end] &＃61; true;
}
}
}
}
return true;
}
public static void main(String[] args) {
System.out.println(new SpfaMyNegativeRing().spfa(new int[][]{{1, 2, 1}, {2, 3, 2}, {1, 3, 5}, {3, 4, 1},
{2, 1, -1}}, 4));
}
}
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 