一文读懂Dijkstra（迪克斯特拉）单源最短路径算法
一文读懂Dijkstra（迪克斯特拉）单源最短路径算法
Dijkstra算法是图论中用于计算单源最短路径的经典算法。本文将从原理、步骤到代码实现，全面解析Dijkstra算法的核心思想和具体应用。
一 概述
在图论中，寻找从一个顶点到另一个顶点的最短路径是一个非常常见的问题。Dijkstra算法主要用于计算带权重图中单源最短路径，即找到从给定起点出发到达其他顶点的最短路径。
二 思路分析
首先不直接给出算法，先想一想如何解决这种问题，我们都知道从数组中求最大值，给定一个临时变量temp，然后遍历数组和temp比较，使得temp每次都保留最大值，最终结果便是最大值。根据这种思想，我们也可以每次遍历图的顶点的时候，都比较一下计算出的距离和当前顶点保存的距离，保存距离小的值，最终遍历完所有的顶点，便得出了从起点到其它顶点的最短路径，本质上是一种贪心算法。
三 实例分析
如图所示，如何找到从V1作为起点到其它节点的最短路径呢？
先说明一下，每个节点都有一个属性dist代表最短路径,每条边都有权重weight代表距离
第一步：初始化，设定起始节点的最短路径dist为0，其余节点的最短路径dist为无穷大
第二步：从未被访问过的节点中选出距离最小的一个节点，这里是V1，检查这个节点能直接到达的所有邻居节点，可以看到是V6，V2，V3。
第三步，遍历的所有邻居，计算邻居的距离(dist+weight)，即当前节点的最短路径+边的权重（如果计算的距离小于邻居本身的距离，则更新），可以看出距离最短的是V2。
V6 0+14=14
V2 0+7=7
V3 0+9=9
第四步：把V2当做选中的节点。V6和V3作为未处理的节点，V1则作为已处理过的节点,继续这个步骤
划重点：这三个概念很重要，选中的节点就是当前dist最小的节点（目前是V2，因为V1已经处理过，不包含V1），未处理的节点就是已经计算出dist，但是不是目前的最短路径的节点（V6，V3），已处理过的节点就是曾经成为最短路径的节点(V1)。
（1）接下来计算V2邻居的距离：
V4 7+15=22
此时未处理的节点，最短路径的节点是V3
V6 14
V4 22
V3 9
（2）继续计算V3的邻居V2和V4，由于V2是被处理过的节点，它的距离是7，我们这里其实没有必要再计算V2的距离了，因为被处理过的节点作为曾经的最短路径，肯定比现在计算的值要小（不考虑负权重的情况），因此这里只计算V4的距离（代码实现的时候直接会跳过V2）
V4 9+11=20
由于20小于22，更新V4的距离为20，此时未处理的节点
V6 14
V4 20
（3）选择V6作为选中的节点，最终计算出V5的最短路径是14+9=23
（4）继续计算其它节点的最短路径，直到没有未处理节点
四 步骤
好了思想有了，接下来想一想步骤，步骤对于写算法很重要，思路不清晰，代码大概率也是有问题的，最好写代码时每次都把步骤列出来，闲话少说，上步骤
1 初始化
设定起始节点的最短路径为0，其余节点的最短路径为无穷大
2 选择
从未处理节点中挑选出具有最小临时距离值的节点
3 更新
对于当前节点u的每一个邻居节点v，检查通过u到达v的距离（即dist[u] + weight(u, v)，其中weight(u, v)是边uv的权重）是否比已知的dist[v]小。如果更小，则更新dist[v]为新的更低的距离值
4 重复
重复步骤2和3，当没有剩余未处理的节点时，算法结束
五 代码
接下来上代码，先看下类的数据结构
/**
* 节点
*/
public class Vertex {
public String name;
/**
* 节点的最短路径，初始化为整数最大值
*/
public int dist = Integer.MAX_VALUE;
/**
* 标记节点为是否已访问过，避免重复处理
*/
public boolean visited;
public List<Edge> edges = new ArrayList<>();
public Vertex(String name) {
this.name = name;
}
@Override
public String toString() {
return "Vertex{" +
"name='" + name + '\'' +
'}';
}
}
/**
* 边
*/
public class Edge {
public Vertex linked;
public int weight;
public Edge(Vertex linked, int weight) {
this.linked = linked;
this.weight = weight;
}
}
/**
* 图
*/
public class Graph {
public final Map<String, Vertex> vertices = new HashMap<>();
/**
* 将指定名称的节点放入map
* @param name 节点名称
* @return 存放的节点
*/
public Vertex getOrCreateVertex(String name) {
return vertices.computeIfAbsent(name, Vertex::new);
}
/**
* 添加节点和边
* @param source 源节点
* @param target 目标节点
* @param weight 边的权重
*/
public void addEdge(String source, String target, Integer weight) {
Vertex sourceVertex = getOrCreateVertex(source);
Vertex targetVertex = getOrCreateVertex(target);
sourceVertex.edges.add(new Edge(targetVertex, weight));
}
}
接下来是算法的具体实现
public class Dijkstra {
public static void main(String[] args) {
Graph graph = new Graph();
graph.addEdge("v1", "v3", 9);
graph.addEdge("v1", "v2", 7);
graph.addEdge("v1", "v6", 14);
graph.addEdge("v2", "v4", 15);
graph.addEdge("v3", "v4", 11);
graph.addEdge("v3", "v2", 2);
graph.addEdge("v4", "v5", 6);
graph.addEdge("v6", "v5", 9);
Vertex source = graph.getOrCreateVertex("v1");
minDist(source);
Vertex target = graph.getOrCreateVertex("v5");
System.out.println(target.dist);
}
public static void minDist(Vertex start) {
start.dist = 0;
// 使用小顶堆存放未处理的节点，提高查找最短路径的性能
PriorityQueue<Vertex> queue = new PriorityQueue<>(Comparator.comparing(o1 -> o1.dist));
queue.add(start);
while (!queue.isEmpty()) {
// 最短路径的节点
Vertex current = queue.poll();
// 如果已经处理过，则跳过
if (current.visited) {
continue;
}
// 标记为已处理
current.visited = true;
// 遍历邻居
for (Edge edge : current.edges) {
Vertex neighbor = edge.linked;
// 计算邻居的距离
int potentialDist = current.dist + edge.weight;
// 判断是否更新邻居的最短路径
if (potentialDist < neighbor.dist) {
neighbor.dist = potentialDist;
// 如果更新了邻居的最短路径，说明邻居可以作为未处理的节点加入堆
queue.add(edge.linked);
}
}
}
}
}
六 改进
上面只是一个简易版的算法，我们还可以给节点类加上previous信息，每次更新邻居距离时，都记录一下previous，这样可以记录最短路径的具体节点都有哪些。
当然，大家工作中不必自己实现图的数据结构，可以使用第三方的库，比如jgrapht
<dependency>
<groupId>org.jgrapht</groupId>
<artifactId>jgrapht-core</artifactId>
<version>1.2.0</version>
</dependency>
下面是使用类库提供的算法，效果是一样的
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleDirectedWeightedGraph;
public class Test {
public static void main(String[] args) {
SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
// 添加顶点
String v1 = "v1";
String v2 = "v2";
String v3 = "v3";
String v4 = "v4";
String v5 = "v5";
String v6 = "v6";
graph.addVertex(v1);
graph.addVertex(v2);
graph.addVertex(v3);
graph.addVertex(v4);
graph.addVertex(v5);
graph.addVertex(v6);
// 添加边
DefaultWeightedEdge edge12 = graph.addEdge(v1, v2);
graph.setEdgeWeight(edge12, 7.0);
DefaultWeightedEdge edge16 = graph.addEdge(v1, v6);
graph.setEdgeWeight(edge16, 14.0);
DefaultWeightedEdge edge13 = graph.addEdge(v1, v3);
graph.setEdgeWeight(edge13, 9.0);
DefaultWeightedEdge edge24 = graph.addEdge(v2, v4);
graph.setEdgeWeight(edge24, 15.0);
DefaultWeightedEdge edge34 = graph.addEdge(v3, v4);
graph.setEdgeWeight(edge34, 11.0);
DefaultWeightedEdge edge23 = graph.addEdge(v2, v3);
graph.setEdgeWeight(edge23, 2.0);
DefaultWeightedEdge edge45 = graph.addEdge(v4, v5);
graph.setEdgeWeight(edge45, 6.0);
DefaultWeightedEdge edge65 = graph.addEdge(v6, v5);
graph.setEdgeWeight(edge65, 9.0);
// 使用 Dijkstra 算法计算最短路径
DijkstraShortestPath<String, DefaultWeightedEdge> dijkstraAlg = new DijkstraShortestPath<>(graph);
double distance = dijkstraAlg.getPath(v1, v5).getWeight();
System.out.println("Shortest path from v1 to v5 has a weight of " + distance);
}
}
七 思考
最后对于负权重的情况，Dijkstra算法无能为力，大家可以思考一下原因（已经黄色加粗给过提示了），以及如何解决，尝试自己思考出如何实现贝尔曼-福特算法（Bellman-Ford）