前言
在本系列第一期:从零开始的图论讲解(1)——图的概念,图的存储,图的遍历与图的拓扑排序-CSDN博客
笔者给大家介绍了 图的概念,如何存图,如何简单遍历图,已经什么是图的拓扑排序
按照之前的学习规划，今天笔者将继续带大家深入了解图论中的一个核心问题：最短路径的求解。
博客将聚焦介绍Dijkstra 算法，这是解决单源最短路径问题中最经典、应用最广泛的算法之一。
博客中出现的参考图都是笔者手画的,代码示例也是笔者手敲的!影响虽小,但请勿抄袭
什么是最短路径问题
在具体介绍算法之前,我先给刚学习的读者简单科普一下什么是最短路径问题,简单来说，
最短路径问题的核心就是：
在一个图中，找到从起点出发，到达终点的路径，使路径的总权值最小。
这里的图可以是有向图，也可以是无向图,这里的权值也代表很多意思,抽象地说,就是代表达到两点之间的代价,比如路程、时间、费用等。
在地图导航中，寻找从出发地到目的地的最短行驶距离；
在网络通信中，找到数据包传输延迟最小的路径；
在项目管理中，计算最短的工期安排。
根据具体场景的不同，最短路径问题还可以细分为几种类型：
1. 单源最短路径：从一个指定节点出发，计算它到其他所有节点的最短路径。
2. 多源最短路径：计算任意两点之间的最短路径。
3. 单对最短路径：只关心从一个节点到另一个节点的最短路径。
在本篇博客中，我们将专注于介绍单源最短路径问题，并学习如何使用经典的Dijkstra 算法来高效解决这一问题。
什么是Dijkstra 算法
Dijkstra 算法是由荷兰计算机科学家艾兹赫尔·迪克斯特拉（Edsger W. Dijkstra）在1959年提出的。它是一种贪心思想的算法，专门用来计算从一个起点到图中其他所有节点的最短路径，前提是：
图的所有边权值必须是非负数,如果有权值是负数,那么有另外的算法去解决,我们以后再谈.
Dijkstra 算法的特点：
适用于无向图或有向图。
可以快速找到单源最短路径，效率优良，且思路简单。
常与优先队列（堆）配合，进一步优化性能,我们先介绍基础算法,然后再介绍用小根堆优化过的算法.
Dijkstra 算法的核心思想 :
Dijkstra 算法的核心思想就是：
1.先选择好起点.
2.每次访问距离起点最近的,且之前没有被访问过的点
3.更新它的邻居的最短路径，并将其标记为已访问。
具体的步骤是:
1.解决最短路径问题时，我们通常要记录从起点到各个节点的当前最短距离。
因此，可以创建一个dist[]数组，长度为节点数量 + 1。数组含义：
dist[i]表示起点start到第i个节点的最短距离。起点
dist[start] = 0，表示从起点到自己，距离为 0。其余节点初始值设置为
∞（通常用Integer.MAX_VALUE或自定义的INF），表示“暂时不可达”。如果算法结束后，
dist[i]仍然是∞，则说明：起点无法到达节点i。同时，还需要一个
vis[]数组用于标记节点是否已经确定了最短路径：
vis[i] = false：表示节点i还未确定最短路径。
vis[i] = true：表示节点i的最短路径已确定，无需再次更新。2.在执行算法之前，必须先完成图的存储。
可以使用两种方式存储图：
邻接表：适合稀疏图，节省空间。
邻接矩阵：适合稠密图，查询方便。
构建完成后，图的结构应该已经完整地反映每个节点的所有出边。
3.构图完成后,开始进行 Dijkstra 算法:
private static void dijkstra(int start) { Arrays.fill(dis,INF); dis[start] = 0; for(int i=1;i<=n;i++) { int pd = -1; int minDist = INF; // 找到当前未访问的点中，距离最小的点 for(int j=1;j<=n;j++) { if(!vis[j] && dis[j] < minDist) { pd = j; minDist = dis[j]; } } // 如果 pd == -1，说明所有点都被访问完了 if(pd==-1) break; vis[pd] = true; // 遍历 pd 的所有邻接点 for(Edge edge : graph.get(pd)) { int v = edge.v; int w = edge.w; if(dis[pd] + w < dis[v]) { dis[v] = dis[pd] + w; } } } }
每次循环，都会从未访问的节点中，选择
距离起点最近的节点pd。如果
pd == -1，说明所有节点都已被访问，或者剩下的节点无法从起点到达，算法提前结束。选中
pd后，遍历它的邻接点，尝试通过pd更新这些点的最短路径：
dis[v] = min(dis[v], dis[pd] + w);这里
dis[pd] + w代表：
“从起点先走到pd，再从pd走到v” 的路径长度。如果这条路径更短，就用它更新
dis[v]，确保每次记录的都是当前已知的最短路径。以上就是朴素版的Dijkstra 算法的具体步骤,接下来我们给一组例子,模拟一遍该算法,让您看的更明白
如图:
假设我们令 1 为源点strat,求 1 到其他点的最短路径,现在我们用Dijkstra 算法模拟一遍
初始状态：
| 点编号 | dist[] 数组值 | vis[] 状态 |
|---|---|---|
| 1 | 0 | false |
| 2 | ∞ | false |
| 3 | ∞ | false |
| 4 | ∞ | false |
第一轮:距离源点最近的点且i
] = false的节点 : 1
标记
vis[1] = true。遍历邻接点：
到
2的距离0 + 2 = 2，更新dist[2] = 2。到
3的距离0 + 5 = 5，更新dist[3] = 5。
点编号 dist[] 数组值 vis[] 状态 1 0 true 2 2 false 3 5 false 4 ∞ false
第二轮: 距离源点最近的点且i
] = false的节点 : 2
标记
vis[2] = true。遍历邻接点：
到
3的距离2 + 1 = 3，比原来的5小，更新dist[3] = 3。到
4的距离2 + 2 = 4，更新dist[4] = 4。此时我们可以看到,借节点2到达3所需要的权值更小,体现出了Dijkstra算法的作用
点编号 dist[] 数组值 vis[] 状态 1 0 true 2 2 true 3 3 false 4 4 false
第三轮: 距离源点最近的点且i
] = false的节点 : 3
标记
vis[3] = true。遍历邻接点：
到
4的距离3 + 3 = 6，但dist[4]已经是4，所以不更新。请注意,虽然节点2也和节点3邻接,但是此时的dist[2] 已经是最优解了
为什么?
因为在第二轮时：
首先:节点2被选中，
dist[2] = 2，说明在所有未访问的点中，从源点出发，能到2的路径已经是全局最短。这时候就把vis[2]设置成true，表明节点2已经确定了最短路径。其次:Dijkstra 的算法核心原则就是
一旦某个节点
i被选择，并且vis[i] = true，说明dist[i]的值已经是最终确定的最小值，不会再被改变。在第一轮时,选择1也不会改变也是同理
点编号 dist[] 数组值 vis[] 状态 1 0 true 2 2 true 3 3 true 4 4 false
第四轮:选出未访问且距离最小的点：节点4
标记
vis[4] = true。由于前面的点都已经确定最短路径,因此没有可维护的节点
点编号 dist[] 数组值 vis[] 状态 1 0 true 2 2 true 3 3 true 4 4 true
最终结果：
| 点编号 | 最短距离 dist[] |
|---|---|
| 1 | 0 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
完整代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Dijkstra
{
static int n,m;
static int N = 505;
final static int INF = Integer.MAX_VALUE-200000000;
static List<List<Edge>> graph = new ArrayList<>();
static boolean[] vis = new boolean[N];
static int[] dis = new int[N];
// 定义一个边的类 (u->v,权值w)
static class Edge {
int v, w;
Edge(int v, int w) {
this.v = v;
this.w = w;
}
}
// 添加一条 u -> v, 权值为 w 的边
static void addEdge(int u, int v, int w)
{
graph.get(u).add(new Edge(v,w));
}
// Dijkstra 算法
private static void dijkstra(int start)
{
Arrays.fill(dis,INF);
dis[start] = 0;
for(int i=1;i<=n;i++)
{
int pd = -1;
int minDist = INF;
// 找到当前未访问的点中，距离最小的点
for(int j=1;j<=n;j++)
{
if(!vis[j] && dis[j] < minDist)
{
pd = j;
minDist = dis[j];
}
}
// 如果 pd == -1，说明所有点都被访问完了
if(pd==-1) break;
vis[pd] = true;
// 遍历 pd 的所有邻接点
for(Edge edge : graph.get(pd))
{
int v = edge.v;
int w = edge.w;
if(dis[pd] + w < dis[v])
{
dis[v] = dis[pd] + w;
}
}
}
}
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
// 提前创建 n+1 个 ArrayList，避免越界
for(int i=0;i<=n;i++) {
graph.add(new ArrayList<>());
}
for(int i=0;i<m;i++)
{
int a = scanner.nextInt();
int b = scanner.nextInt();
int c = scanner.nextInt();
addEdge(a,b,c);
}
dijkstra(1);
if(dis[n]>=INF-100000000)
{
System.out.println(-1);
}
else
{
System.out.println(dis[n]);
}
}
}
如何优化Dijkstra 算法?
我们可以看到
for(int i=1;i<=n;i++)
{
int pd = -1;
int minDist = INF;
// 找到当前未访问的点中，距离最小的点
for(int j=1;j<=n;j++)
{
if(!vis[j] && dis[j] < minDist)
{
pd = j;
minDist = dis[j];
}
}
// 如果 pd == -1，说明所有点都被访问完了
if(pd==-1) break;
vis[pd] = true;
// 遍历 pd 的所有邻接点
for(Edge edge : graph.get(pd))
{
int v = edge.v;
int w = edge.w;
if(dis[pd] + w < dis[v])
{
dis[v] = dis[pd] + w;
}
}
}内层寻找最小点的部分： O(n^2)
遍历边的部分:O(m)，但这个通常远小于 O(n^2)，所以主导复杂度是 O(n^2)。
如何优化呢?
在朴素版 Dijkstra 中，我们每次都需要从未访问过的点中，找到距离源点最近的节点，然后进行标记和松弛操作。这个寻找过程使用 O(n) 的循环，显然效率不高。
为了优化这一过程，我们可以使用小根堆来维护当前所有未访问的候选节点。每当我们遍历邻接点并更新 dist[] 时，就将这些点加入小根堆。堆顶的元素总是当前到源点距离最小的节点，因此每次从堆里取出的节点，正好就是下一个要访问的目标。
需要注意的是，由于同一个节点在更新路径时可能会多次入堆，实际取出时，可能会遇到这个节点已经被访问过的情况。因此，在正式处理之前，我们要加一个判断：
如果当前节点已经被访问过，直接
continue，跳过它，继续从堆中取下一个节点。
代码如下:
import java.util.*;
public class BetterperformanceDijkstra {
static class Node
{
public int v;
public int w;
public Node(int v, int w) {
this.v = v;
this.w = w;
}
}
static int n,m;
static List<List<Node>> list = new ArrayList<>();
public static void addEge(int u, int v, int w)
{
list.get(u).add(new Node(v,w));
}
static boolean[] vis;
static int[] dist;
static final int INF = Integer.MAX_VALUE-20000000;
public static void dijkstra(int start)
{
Arrays.fill(dist,INF);
dist[start] = 0;
PriorityQueue<Node> priorityQueue = new PriorityQueue<>(((o1, o2) -> o1.w-o2.w));
Node cur = new Node(start,0);
priorityQueue.offer(cur);
while(!priorityQueue.isEmpty())
{
Node temp = priorityQueue.poll();
int v = temp.v;
int w = temp.w;
if(vis[v])
{
continue;//已经访问过了
}
vis[v] = true;
if(list.get(v)==null)
{
continue;//没有联通的点
}
for(Node tep : list.get(v))
{
int vi = tep.v;
int wi = tep.w;
if(dist[vi]>dist[v]+wi)//维护最短路径
{
dist[vi] = dist[v]+wi;
priorityQueue.offer(new Node(vi,dist[vi]));
}
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
for(int i=0;i<=n;i++)
{
list.add(new ArrayList<>());
}
vis = new boolean[n+1];
dist = new int[n+1];
for(int i=0;i<m;i++)
{
int a = scanner.nextInt();
int b = scanner.nextInt();
int c = scanner.nextInt();
addEge(a,b,c);
}
dijkstra(1);
System.out.println(dist[n]==INF?"-1":dist[n]);
}
}
结尾
结尾笔者留几个题目给大家练手
3112. 访问消失节点的最少时间 - 力扣（LeetCode）
希望本博客对大家来说有收获,也不枉我分享出来!!!谢谢大家