笔记总结
最短路问题一般分为两种:单源最短路,多源汇最短路
单源最短路:一个点到第n个点的距离,单源路问题又可以分为两个问题(n表示点数,m表示边数)
- 所有边权都是正数:
- 朴素Dijkstra算法O(n^2^):适合稠密图,也就是边多的图,m和n^2^是一个级别,因为和边没有关系
- 堆优化版的Dijkstra算法O(mlogn):适合稀疏图,m和n是一个级别
- 存在负权边
- Bellman-Ford算法:O(nm),用于不超过k条边的最短路
- SPFA算法:O(m)最坏时间复杂度O(nm)
多源汇最短路:源:起点,汇:终点,指的是起点不止一个
- Floyd算法:O(n^3^)
算法思想
迭代n次,每次迭代都可以确定一个距离起点最短的点,迭代n次后,n就是距离起点最短的点
算法步骤
- 初始化距离,
g[i][j]
= 0x3f3f,d[i] = 0x3f3f,d[1] = 0
2:迭代n次去确定每个点距离起点的最小值,每迭代一次都可以确定一个距离最短的点
3:循环每个点,用t更新其他点的距离
学习步骤
如果是第一次学习这些算法,第一遍挺肯定会懵懂的,一知半解,这是很正常的,不是自己笨,而是前人花费多年时间总结出来的算法,总不能让自己一下子学会,那他们也太没面子了;
所以听了y总的讲解后,要自己深入代码,拿着实例去代码中试一试,只听不思考那始终都是y总的知识,也不是自己的,一定要有自己的思考
问题详解
有三个问题
- t = -1的作用
- 问题2:
if (!st[j] && (t == -1 || dist[t] > dist[j]))
的作用 - 问题3:
dist[j] = min(dist[j], dist[t] + g[t][j]);
的作用
问题实例
问题1:t = -1的作用
只是为了在剩下还没有确定最短距离的点中,更新t的值,在这里取比1小都是可以的
比如说1已经确定最短距离了,st[1] = true,所以1会直接跳出if判断
然后开始判断第二个点,2还没有确定,t == -1,所以t 会直接等于 2
然后判断第三个点,3还没有确定,然后判断dist[2] > dist[3],答案是dist[2] < dist[3],所以t = 2;
问题2:if (!st[j] && (t == -1 || dist[t] > dist[j]))
的作用
1:看剩下的点中谁还没有确定最短距离
2:这些点中谁距离起点最短
所以经历过这个判断后,t就是距离起点最短的点,所以说就可以st[t] = true
每次迭代的过程都是先找到当前未确定最短距离的点中,距离最短的点
!st[j]看的是这个点是否是false,也就是还没有确定最短距离
问题3:dist[j] = min(dist[j], dist[t] + g[t][j]);
的作用
更新每个点到起点的距离
比如说,t = 2,
dist[1] = min(dist[1],dist[2] + g[2][1]
:因为g[2][1]
= 0x3f3f,所以肯定是dist[1]小
dist[2] = min(dist[2],dist[2] + g[2][2]
:因为g[2][2]
= 0x3f3f,所以肯定是dist[2]小
dist[3] = min(dist[3],dist[2] + g[2][3]
:因为dist[3] = 4,dist[2] + g[2][3]
= 1 + 2 = 3,所以更新为3
Java代码
import java.util.Scanner;
import java.util.Arrays;
public class Main
{
static int N = 510;
static int[][] g = new int[N][N];
static int[] dist = new int[N]; //以每个节点为索引,存储从1号点到n号点的当前最短距离
static boolean[] st = new boolean[N]; //表示每个点当前的最短距离是否已经确定了
static int n;
public static void main(String[] args)throws Exception
{
Scanner in = new Scanner(System.in);
n = in.nextInt();
int m = in.nextInt();
for(int i = 0; i < n; i ++) Arrays.fill(g[i],0x3f3f); //每个数组都填充为最大值
while(m-- > 0)
{
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
g[a][b] = Math.min(g[a][b],c); //如果存在重边,只用保存最短的内条边就可以了
}
System.out.print(dijkstra());
}
private static int dijkstra()
{
for(int i = 0; i < N; i ++) dist[i] = 0x3f3f;
dist[1] = 0;
for(int i = 0; i < n; i ++) //循环n次
{
int t = -1;
for(int j = 1; j <= n; j++) //循环每个点
{
if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j; //还没有确定最短路
}
for(int j = 1; j <= n; j ++)
{
dist[j] = Math.min(dist[j],dist[t] + g[t][j]);
}
st[t] = true;
}
if(dist[n] == 0x3f3f) return -1;
return dist[n];
}
}
问题技巧
如何把一个数组全部填充为一个数
import java.util.Arrays;
//填充一维数组
Arrays.fill(a,-1);
//填充二维数组 可以把二维数组看出一个一维数组,数组中包含着一维数组,然后把每个小数组进行填充
[[0,0,0,0],[0,0,0,0],[0,0,0,0]]
for(int i = 0; i < n; i ++) Arrays.fill(a[i],-1);