分类
Dijkstra - 正有权图
朴素Dijkstra
849. Dijkstra求最短路 I - AcWing题库
O(n^2)
思路
准备
- 稠密图
m >> n
用邻接矩阵table[a][b]
保存两条边之间的路径, 初始无穷大 - 用一个 dist 数组保存源点到其余各个节点的距离,dist[i] 表示源点到节点 i 的距离。初始时,dist 数组的各个元素为无穷大。
- 用一个状态数组 state 记录是否找到了源点到该节点的最短距离,state[i] 如果为真,则表示找到了源点到节点 i 的最短距离,state[i] 如果为假,则表示源点到节点 i 的最短距离还没有找到。初始时,state 各个元素为假。
- 遍历 dist 数组,找到一个节点,这个节点是:没有确定最短路径的 节点中距离起点最近的点。
最终目标就是 按照距离起点 距离大小 将所有点都取出来一遍 O(n)
假设该节点编号为 i , 用 first 记录。此时就找到了源点到该节点的最短距离,state[first]
置为 true
- 枚举 first 所有可以到达的节点 j,如果 dist[j] 大于 dist[first] 加上
first -> j
的距离,
即 dist[j] > dist[i] + w[i][j]
(w[i][j] 为 i -> j
的距离) ,
则更新 dist[j] = dist[i] + w[i][j]
。 O(n)
- 重复 1 2 步骤,直到所有节点的状态都被置为 1。
int dist[n + 1],state[n + 1];
dist[1] = 0;
for(i:1 ~ n)
{
first <- 没有确定最短路径的节点中距离源点最近的点 (没有取出来用过);
state[first] = true;
for(j:1 ~ n)
满足条件 则更新dist;
}
实现
import java.io.*;
import java.util.*;
public class Main {
static int n, table[][]; // 边数太多 邻接矩阵, 记录两点间距离
static int dist[]; // 每个点到 起点最短距离
static boolean state[]; // 记录是否找到 起点到该节点的最短距离
// 朴素迪杰斯特拉 求单源最短路
static int dijkstra(int x) {
// 初始化距离数组
Arrays.fill(dist, 0x3f3f3f3f);
dist[x] = 0; // 起点
// 1. 迭代n次
for(int i = 1; i <= n; i++) {
int fisrt = -1; // 2. 记录距离起点最近的点
// 3. 枚举所有点, 更新first
for(int j = 1; j <= n; j++)
// j未确定最短距, 且j比fist距离起点更近
if(!state[j] && (fisrt == -1 || dist[fisrt] > dist[j]))
fisrt = j; // 更新first
// 标记
state[fisrt] = true;
// 4. 枚举所有点, 起点经过fist到j近 还是原dist近
for(int j = 1; j <= n; j++)
// dist[j]原来到起点距离
// dist[fisrt] + table[fisrt][j] : 起点到first再到该点距离
// 所以table和dist 初始化int最大值/2, 否则可能溢出
dist[j] = Math.min(dist[j], dist[fisrt] + table[fisrt][j]);
}
if(dist[n] == 0x3f3f3f3f)
return -1;
else
return dist[n];
}
public static void main(String[] args) throws Exception {
Read sc = new Read();
n = sc.nextInt();
int m = sc.nextInt();
table = new int[n + 1][n + 1];
dist = new int[n + 1];
state = new boolean[n + 1];
for(int i = 0; i <= n; i++)
// 最大值/2, 避免出现溢出 或者赋值为 0x3f3f3f3f
Arrays.fill(table[i], 0x3f3f3f3f);
while(m-- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
// 题意: 可能存在重边 取最小即可
table[a][b] = Math.min(table[a][b], c);
}
System.out.print(dijkstra(1));
}
}
// 快读
class Read {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public int nextInt() throws Exception {
st.nextToken();
return (int) st.nval;
}
}
优化Dijkstra
850. Dijkstra求最短路 II - AcWing题库
思路
O(m log n)
- 使用 优先队列 存储 节点到起点的距离, 构建小根堆 , 替代原来第一步的遍历 dist 数组,
按距离大小将所有点取出来一遍, 该步时间复杂度 从 O(n)
降为O(log n)
-
第二步 枚举对所有与 fisrt 相连的节点 进行 dist 更新, 时间复杂度 从
O(n)
==>O(m)
-
稀疏图 使用 邻接表(+单链表) 存储节点, 多加一个
w[]
存储两点间距离
import java.io.*;
import java.util.*;
public class Main {
// 稀疏图 使用邻接表存储, w存储节点间距离
static int n, table[], value[], next[], w[], index;
static int dist[];
static boolean state[];
static void add(int a, int b, int c) {
value[index] = b;
w[index] = c; // 距离
next[index] = table[a];
table[a] = index++;
}
// 优先队列 优化版迪杰斯特拉
// 使用优先队列替代 原先枚举dist操作 --> O(log m)
static int dijkstra(int x) {
// 从小到大排序 构建小根堆
Queue<Node> heap = new PriorityQueue<>();
heap.offer(new Node(1, 0));
Arrays.fill(dist, Integer.MAX_VALUE / 2);
dist[x] = 0;
while(!heap.isEmpty()) {
Node node = heap.poll(); // 原来的first, 距离起点最近的节点
int first = node.id, distance = node.length;
if(state[first]) // 已经取出来过, 跳过
continue;
state[first] = true;
// 遍历节点first 的邻接表, 更新其他点到起点距离
for(int i = table[first]; i != -1; i = next[i]) {
int second = value[i];
// 从first走过来更近
if(dist[second] > dist[first] + w[i]) {
dist[second] = dist[first] + w[i];
// 入队
heap.offer(new Node(second, dist[second]));
}
}
}
if(dist[n] == Integer.MAX_VALUE / 2)
return -1;
else
return dist[n];
}
public static void main(String[] args) throws Exception {
Read sc = new Read();
n = sc.nextInt();
int m = sc.nextInt();
table = new int[n + 1];
Arrays.fill(table, -1);
value = new int[m + 1];
next = new int[m + 1];
w = new int[m + 1];
dist = new int[n + 1];
state = new boolean[n + 1];
while(m-- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
add(a, b, c); // 邻接表 无需解决重边问题
}
System.out.print(dijkstra(1));
}
}
// 节点类 优先队列构建小根堆
class Node implements Comparable<Node> {
int id; // 节点编号
int length; // 距离
public Node(int id, int length) {
this.id = id;
this.length = length;
}
public int compareTo(Node node) {
return this.length - node.length; // 从小到大排序
}
}
// 快读
class Read {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public int nextInt() throws Exception {
st.nextToken();
return (int) st.nval;
}
}
Bellman-Ford - 负权图
- 可以判断是否存在 负环: 一条边权之和为负数的回路
该算法可以判断负环, 避免死循环
- 不过少用, 找负环 优先使用SPFA算法
思路
O(n m)
特殊 : 除了有边数限制 只有ford能用, 其余 负权图 题目使用 spfa 算法更好
import java.util.*;
public class Main {
static int n, m, k;
// dist每个节点到起点距离 backup备份数组
static int dist[], backup[];
static Node[] nodes; // 节点数组
static boolean bellman_ford(int x) {
Arrays.fill(dist, Integer.MAX_VALUE / 2);
dist[x] = 0;
// 枚举k条边
for(int i = 1; i <= k; i++) {
// 备份上一次循环 的数组
backup = Arrays.copyOf(dist, n + 1);
// 枚举所有边, 更新最短距离
for(int j = 0; j < m; j++) {
Node node = nodes[j];
int a = node.a, b = node.b, w = node.w;
// 上一次的数据进行比较
dist[b] = Math.min(dist[b], backup[a] + w);
}
}
if(dist[n] > Integer.MAX_VALUE / 4)
return false;
else
return true;
}
public static void main(String[] argd) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
k = sc.nextInt();
nodes = new Node[m + 1];
dist = new int[n + 1];
for(int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int w = sc.nextInt();
nodes[i] = new Node(a, b, w);
}
if(bellman_ford(1))
System.out.print(dist[n]);
else
System.out.print("impossible");
}
}
// 节点类 保存每一条边
class Node {
int a, b, w;
public Node(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}
}
SPFA - 负权优先使用
==一般O(m)
最坏O(nm)
==
求最短路
思路
-
在 Ford 算法基础上进行 堆优化, 代码模板 和迪杰斯特拉算法 很相似
-
使用邻接表 存储, 存储方式和 dijkstra 相同
-
迪杰斯特拉 是用==最短的边== PriorityQueue 去更新其他边,
而spfa 是上次更新的终点 Queue 去更新其他边,
贝尔曼 则是非常暴力的每次更新所有边
负权边处理: 一开始没有负权边,如果存在负权边,那么负权边的终点会入队,a的出度边的终点会再次更新
使用队列Queue存储节点编号 对ford算法的 最外层for循环优化
// spfa 算法使用Queue, 每次取出上一次更新的点, 再去更新其他边
// 而 dj 是使用 PriorityQueue, 每次取出距离起点最近的点 去更新其他边
while queue不空
first 出队
state 标记该点不在队列
for 循环邻接表
取出和 first 相连的点second 边
若经过 first 到 second 更短
更新距离
若second 不在队列, 入队
实现
与dijkstra 模板区别
- 该代码使用 Queue , dj 使用 优先队列
- spfa 每次取出的是上一次更新的点
- dj 每次取出的是 距离起点最近的点
- state[] 含义不同, 该代码标记 节点是否在队列, 一旦节点出队标记false, 入队标记 true
结果: 代码相近, 但 spfa 能处理负权边
import java.util.*;
public class Main {
// 稀疏图, 用邻接表存储
static int n, m, table[], value[], next[], w[], index;
static int dist[]; // 到起点距离
static boolean state[]; // 标记节点是否在队列(与dj不同)
static void add(int a, int b, int c) {
value[index] = b;
w[index] = c;
next[index] = table[a];
table[a] = index++;
}
// 整个模板与dj相近, 只有该方法有区别
static boolean spfa(int x) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(x);
state[x] = true; // x在队列中
Arrays.fill(dist, Integer.MAX_VALUE / 2);
dist[x] = 0;
while(!queue.isEmpty()) {
int first = queue.poll(); // 首节点出队
// 注意: 节点出队, 标记false!!! 与dj不同
state[first] = false;
for(int i = table[first]; i != -1; i = next[i]) {
int second = value[i];
// 经过first 过来更快
if(dist[second] > dist[first] + w[i]) {
dist[second] = dist[first] + w[i];
// 注意: 比dj区别 在state
if(!state[second]) { // 节点不在队列
queue.offer(second);
state[second] = true;
}
}
}
}
if(dist[n] > Integer.MAX_VALUE / 4) // 可能存在负权
return false;
else
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
table = new int[n + 1];
Arrays.fill(table, -1);
value = new int[m + 1];
next = new int[m + 1];
w = new int[m + 1];
dist = new int[n + 1];
state = new boolean[n + 1];
while(m-- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
add(a, b, c);
}
if(spfa(1))
System.out.print(dist[n]);
else
System.out.print("impossible");
}
}
判断负环
-
判断负环 新增一个数组
cnt[]
, 维护起点到当前节点 边数 即可 -
初始时, 将所有点 入队, 从第一个出发不一定经过负环
// spfa 算法判断负环
static boolean spfa() {
Queue<Integer> queue = new LinkedList<>();
// 循环所有点入队 从所有点出发, 才能判断有没有负环
// 所有点出发, dist都为0, 无需初始化
for(int i = 1; i <= n; i++) {
queue.offer(i);
state[i] = true; //标记入队
}
while(!queue.isEmpty()) {
int first = queue.poll();
state[first] = false; // 出队
for(int i = table[first]; i != -1; i = next[i]) {
int second = value[i];
// 更新距离 边数cnt
if(dist[second] > dist[first] + w[i]) {
dist[second] = dist[first] + w[i];
cnt[second] = cnt[first] + 1;
// 有节点重复经过, 存在负环
if(cnt[second] >= n)
return true;
if(!state[second]) {
queue.offer(second);
state[second] = true;
}
}
}
}
return false; // 不存在负环
}
Floyd - 多源最短路
注: 可以处理负权, 但不可以有负环
多重背包思想
O(n^3)
-
使用邻接矩阵 存储 两节点的距离
-
使用 dp 动态规划思想 求解
dp[i, x, y]
==>dp[x, y]
i 枚举中间点, x 枚举起点, y 枚举终点
dp[i, x, y]
表示从 i 出发, 经过 1~i 间的所有点 达到 y 的最短距离
- ==适用于稠密图 m >> n, 节点数较少题目==
实现
- 递推方程
static void floyd() {
for(int i = 1; i <= n; i++)
for(int x = 1; x <= n; x++)
for(int y = 1; y <= n; y++)
// x ==> y 与 x ==> i ==> y比较
table[x][y] = Math.min(table[x][y], table[x][i] + table[i][y]);
}
- 初始化 读入
table = new int[n + 1][n + 1];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i == j)
table[i][j] = 0; // 屏蔽 自环
else
// 避免溢出
table[i][j] = Integer.MAX_VALUE / 2;
while(m-- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
// 存最短距离
table[a][b] = Math.min(table[a][b], c);
}