算法详解：Dijkstra算法 - 单源最短路径的经典解法#
在计算机科学和现实生活中，寻找最短路径是一个极其重要的问题。无论是GPS导航寻找最快路线，还是网络协议中数据包的路由选择，或是航空公司规划最经济的航线，都离不开最短路径算法。而在众多最短路径算法中，Dijkstra算法无疑是最经典、最重要的算法之一。
Dijkstra算法由荷兰计算机科学家埃德加·戴克斯特拉（Edsger Dijkstra）在1956年提出，用于解决单源最短路径问题。经过近70年的发展，这个算法依然是现代计算机系统中的核心算法之一。
1. Dijkstra算法基础概念#
1.1 什么是单源最短路径问题#
单源最短路径问题是指：给定一个带权有向图和一个源点，求从源点到图中所有其他顶点的最短路径。这里的"最短"通常指路径上所有边权重的总和最小。
1.2 算法核心思想#
Dijkstra算法采用了贪心策略，其核心思想可以概括为：
- 维护一个距离数组，记录从源点到各个顶点的最短距离
- 每次选择距离最小且未处理的顶点进行松弛操作
- 通过松弛操作不断更新其他顶点的最短距离
- 重复这个过程直到所有顶点都被处理
1.3 图的表示方法#
在实现Dijkstra算法之前，我们需要了解图的表示方法。常用的有两种：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| // 邻接矩阵表示法
int[][] graph = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
// ... 更多行
};
// 邻接表表示法
List<List<Edge>> adjList = new ArrayList<>();
class Edge {
int to;
int weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
|
2. 现实生活中的应用实例#
2.1 GPS导航系统#
当你在手机上输入目的地时，GPS系统就是在使用类似Dijkstra的算法来寻找最短路径：
1
2
3
4
| 起点: 你的当前位置
终点: 目的地
边权重: 道路长度、预计通行时间、交通拥堵程度
目标: 找到时间最短或距离最短的路线
|
2.2 网络路由协议#
在计算机网络中，路由器使用最短路径算法来决定数据包的转发路径：
1
2
3
4
| 起点: 源路由器
终点: 目标路由器
边权重: 链路延迟、带宽、成本
目标: 找到网络延迟最小的路径
|
2.3 航空航线规划#
航空公司在规划航线时也会使用最短路径算法：
1
2
3
4
| 起点: 出发机场
终点: 目的地机场
边权重: 飞行时间、燃油成本、机场费用
目标: 找到成本最低或时间最短的航线
|
3. 算法详细实现#
3.1 基础版本实现#
首先，让我们看一个基础的Dijkstra算法实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| import java.util.*;
public class DijkstraBasic {
private static final int INF = Integer.MAX_VALUE;
/**
* 基础版Dijkstra算法实现
* @param graph 邻接矩阵表示的图
* @param src 源点
* @return 从源点到各点的最短距离数组
*/
public static int[] dijkstra(int[][] graph, int src) {
int n = graph.length;
int[] dist = new int[n]; // 距离数组
boolean[] visited = new boolean[n]; // 访问标记数组
// 初始化距离数组
Arrays.fill(dist, INF);
dist[src] = 0;
// 主循环：处理n个顶点
for (int count = 0; count < n - 1; count++) {
// 找到未访问顶点中距离最小的
int u = minDistance(dist, visited);
visited[u] = true;
// 松弛操作：更新u的邻接顶点的距离
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != 0 &&
dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
return dist;
}
/**
* 找到未访问顶点中距离最小的顶点
*/
private static int minDistance(int[] dist, boolean[] visited) {
int min = INF;
int minIndex = -1;
for (int v = 0; v < dist.length; v++) {
if (!visited[v] && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}
}
|
3.2 优化版本：使用优先队列#
基础版本的时间复杂度是O(V²)，对于稠密图来说是合理的，但对于稀疏图，我们可以使用优先队列来优化：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
| import java.util.*;
public class DijkstraOptimized {
static class Edge {
int to;
int weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
static class Node implements Comparable<Node> {
int vertex;
int distance;
Node(int vertex, int distance) {
this.vertex = vertex;
this.distance = distance;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.distance, other.distance);
}
}
/**
* 使用优先队列优化的Dijkstra算法
* @param graph 邻接表表示的图
* @param src 源点
* @return 从源点到各点的最短距离数组
*/
public static int[] dijkstra(List<List<Edge>> graph, int src) {
int n = graph.size();
int[] dist = new int[n];
boolean[] visited = new boolean[n];
// 初始化距离数组
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// 优先队列，自动按距离排序
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(src, 0));
while (!pq.isEmpty()) {
Node current = pq.poll();
int u = current.vertex;
// 如果已经访问过，跳过
if (visited[u]) continue;
visited[u] = true;
// 松弛操作
for (Edge edge : graph.get(u)) {
int v = edge.to;
int weight = edge.weight;
if (!visited[v] && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.offer(new Node(v, dist[v]));
}
}
}
return dist;
}
/**
* 获取最短路径（不仅仅是距离）
*/
public static List<Integer> getShortestPath(List<List<Edge>> graph, int src, int dest) {
int n = graph.size();
int[] dist = new int[n];
int[] parent = new int[n]; // 记录路径
boolean[] visited = new boolean[n];
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(parent, -1);
dist[src] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(src, 0));
while (!pq.isEmpty()) {
Node current = pq.poll();
int u = current.vertex;
if (visited[u]) continue;
visited[u] = true;
for (Edge edge : graph.get(u)) {
int v = edge.to;
int weight = edge.weight;
if (!visited[v] && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
parent[v] = u; // 记录父节点
pq.offer(new Node(v, dist[v]));
}
}
}
// 重构路径
List<Integer> path = new ArrayList<>();
if (dist[dest] == Integer.MAX_VALUE) {
return path; // 无法到达
}
int current = dest;
while (current != -1) {
path.add(current);
current = parent[current];
}
Collections.reverse(path);
return path;
}
}
|
4. 算法执行过程详解#
让我们通过一个具体的例子来追踪Dijkstra算法的执行过程。
4.1 示例图结构#
考虑以下带权有向图：
1
2
3
4
5
6
7
8
9
10
| 图结构可视化：
7 9
1 -----> 2 -----> 3
| / | |
| / | |
| 14 / | 10 | 11
| / | |
v / v v
5 <----- 4 -----> 6
2 15
|
邻接表表示：
1
2
3
4
5
6
7
8
9
| 0: [(1,4), (7,8)]
1: [(0,4), (2,8), (7,11)]
2: [(1,8), (3,7), (8,2), (5,4)]
3: [(2,7), (4,9), (5,14)]
4: [(3,9), (5,10)]
5: [(2,4), (4,10), (6,2)]
6: [(5,2), (7,1), (8,6)]
7: [(0,8), (1,11), (6,1), (8,7)]
8: [(2,2), (6,6), (7,7)]
|
4.2 逐步执行过程#
假设源点为0，让我们追踪算法的每一步：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| public class DijkstraTrace {
public static void traceExecution() {
// 初始状态
System.out.println("=== Dijkstra算法执行追踪 ===");
System.out.println("源点: 0");
System.out.println();
int[] dist = {0, INF, INF, INF, INF, INF, INF, INF, INF};
boolean[] visited = new boolean[9];
System.out.println("初始距离: " + Arrays.toString(dist));
System.out.println();
// 第1轮：选择顶点0
System.out.println("第1轮：选择顶点0（距离=0）");
visited[0] = true;
// 松弛顶点1: dist[1] = min(INF, 0+4) = 4
dist[1] = 4;
// 松弛顶点7: dist[7] = min(INF, 0+8) = 8
dist[7] = 8;
System.out.println("更新后距离: " + Arrays.toString(dist));
System.out.println("已访问: 0");
System.out.println();
// 第2轮：选择顶点1（距离=4）
System.out.println("第2轮：选择顶点1（距离=4）");
visited[1] = true;
// 松弛顶点2: dist[2] = min(INF, 4+8) = 12
dist[2] = 12;
// 松弛顶点7: dist[7] = min(8, 4+11) = 8（无改变）
System.out.println("更新后距离: " + Arrays.toString(dist));
System.out.println("已访问: 0, 1");
System.out.println();
// 继续其他轮次...
System.out.println("... 继续执行直到所有顶点被处理 ...");
}
}
|
4.3 最终结果#
经过完整执行后，我们得到从顶点0到所有其他顶点的最短距离：
1
2
3
4
5
6
7
8
9
10
| 顶点 最短距离 最短路径
0 0 [0]
1 4 [0, 1]
2 12 [0, 1, 2]
3 19 [0, 1, 2, 3]
4 21 [0, 7, 6, 5, 4]
5 11 [0, 7, 6, 5]
6 9 [0, 7, 6]
7 8 [0, 7]
8 14 [0, 1, 2, 8]
|
5. 高级优化技术#
5.1 双向搜索#
对于点对点的最短路径查询，双向搜索可以显著提高效率：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| public class BidirectionalDijkstra {
public static int bidirectionalSearch(List<List<Edge>> graph,
List<List<Edge>> reverseGraph,
int src, int dest) {
int n = graph.size();
// 正向搜索的距离和访问标记
int[] distForward = new int[n];
boolean[] visitedForward = new boolean[n];
Arrays.fill(distForward, Integer.MAX_VALUE);
distForward[src] = 0;
// 反向搜索的距离和访问标记
int[] distBackward = new int[n];
boolean[] visitedBackward = new boolean[n];
Arrays.fill(distBackward, Integer.MAX_VALUE);
distBackward[dest] = 0;
PriorityQueue<Node> forwardPQ = new PriorityQueue<>();
PriorityQueue<Node> backwardPQ = new PriorityQueue<>();
forwardPQ.offer(new Node(src, 0));
backwardPQ.offer(new Node(dest, 0));
int shortestPath = Integer.MAX_VALUE;
while (!forwardPQ.isEmpty() || !backwardPQ.isEmpty()) {
// 正向搜索一步
if (!forwardPQ.isEmpty()) {
shortestPath = Math.min(shortestPath,
expandNode(forwardPQ, graph, distForward, visitedForward,
distBackward, visitedBackward, true));
}
// 反向搜索一步
if (!backwardPQ.isEmpty()) {
shortestPath = Math.min(shortestPath,
expandNode(backwardPQ, reverseGraph, distBackward, visitedBackward,
distForward, visitedForward, false));
}
// 如果找到了路径，可以提前终止
if (shortestPath < Integer.MAX_VALUE) {
break;
}
}
return shortestPath;
}
private static int expandNode(PriorityQueue<Node> pq, List<List<Edge>> graph,
int[] dist, boolean[] visited,
int[] otherDist, boolean[] otherVisited,
boolean isForward) {
Node current = pq.poll();
int u = current.vertex;
if (visited[u]) return Integer.MAX_VALUE;
visited[u] = true;
// 检查是否与另一方向的搜索相遇
if (otherVisited[u]) {
return dist[u] + otherDist[u];
}
// 松弛操作
for (Edge edge : graph.get(u)) {
int v = edge.to;
int weight = edge.weight;
if (!visited[v] && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.offer(new Node(v, dist[v]));
}
}
return Integer.MAX_VALUE;
}
}
|
5.2 A*算法比较#
A*算法是Dijkstra算法的启发式版本，通过引入启发函数来指导搜索方向：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| public class AStarComparison {
// 启发函数：估算从当前点到目标点的距离
public interface HeuristicFunction {
int estimate(int current, int goal);
}
/**
* A*算法实现
*/
public static List<Integer> aStar(List<List<Edge>> graph, int src, int dest,
HeuristicFunction heuristic) {
int n = graph.size();
int[] gScore = new int[n]; // 从起点到当前点的实际距离
int[] fScore = new int[n]; // gScore + 启发值
int[] parent = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(gScore, Integer.MAX_VALUE);
Arrays.fill(fScore, Integer.MAX_VALUE);
Arrays.fill(parent, -1);
gScore[src] = 0;
fScore[src] = heuristic.estimate(src, dest);
// 优先队列按fScore排序
PriorityQueue<Node> openSet = new PriorityQueue<>(
Comparator.comparingInt(node -> fScore[node.vertex])
);
openSet.offer(new Node(src, fScore[src]));
while (!openSet.isEmpty()) {
Node current = openSet.poll();
int u = current.vertex;
if (u == dest) {
// 找到目标，重构路径
return reconstructPath(parent, dest);
}
if (visited[u]) continue;
visited[u] = true;
for (Edge edge : graph.get(u)) {
int v = edge.to;
if (visited[v]) continue;
int tentativeGScore = gScore[u] + edge.weight;
if (tentativeGScore < gScore[v]) {
parent[v] = u;
gScore[v] = tentativeGScore;
fScore[v] = gScore[v] + heuristic.estimate(v, dest);
openSet.offer(new Node(v, fScore[v]));
}
}
}
return new ArrayList<>(); // 无路径
}
private static List<Integer> reconstructPath(int[] parent, int dest) {
List<Integer> path = new ArrayList<>();
int current = dest;
while (current != -1) {
path.add(current);
current = parent[current];
}
Collections.reverse(path);
return path;
}
}
|
6. 实际应用案例#
6.1 网络分析系统#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| public class NetworkAnalyzer {
public static class NetworkNode {
String id;
String name;
double latitude;
double longitude;
// 构造函数和getter/setter...
}
public static class NetworkLink {
String fromId;
String toId;
double bandwidth; // 带宽（Mbps）
double latency; // 延迟（ms）
double cost; // 成本
// 构造函数和getter/setter...
}
/**
* 网络路径优化器
*/
public static class NetworkPathOptimizer {
private Map<String, Integer> nodeIdToIndex;
private List<NetworkNode> nodes;
private List<List<Edge>> graph;
public NetworkPathOptimizer(List<NetworkNode> nodes, List<NetworkLink> links) {
this.nodes = nodes;
buildGraph(nodes, links);
}
private void buildGraph(List<NetworkNode> nodes, List<NetworkLink> links) {
// 建立节点ID到索引的映射
nodeIdToIndex = new HashMap<>();
for (int i = 0; i < nodes.size(); i++) {
nodeIdToIndex.put(nodes.get(i).id, i);
}
// 构建邻接表
graph = new ArrayList<>();
for (int i = 0; i < nodes.size(); i++) {
graph.add(new ArrayList<>());
}
for (NetworkLink link : links) {
int from = nodeIdToIndex.get(link.fromId);
int to = nodeIdToIndex.get(link.toId);
// 根据不同的优化目标设置权重
int weight = calculateWeight(link);
graph.get(from).add(new Edge(to, weight));
// 如果是无向图，添加反向边
graph.get(to).add(new Edge(from, weight));
}
}
private int calculateWeight(NetworkLink link) {
// 可以根据不同需求计算权重
// 例如：最小延迟、最大带宽、最低成本等
return (int) (link.latency * 100); // 以延迟为主要因素
}
/**
* 查找最优路径
*/
public List<String> findOptimalPath(String sourceId, String destId) {
int source = nodeIdToIndex.get(sourceId);
int dest = nodeIdToIndex.get(destId);
List<Integer> path = DijkstraOptimized.getShortestPath(graph, source, dest);
// 将索引转换为节点ID
return path.stream()
.map(index -> nodes.get(index).id)
.collect(Collectors.toList());
}
/**
* 网络可达性分析
*/
public Map<String, Integer> analyzeReachability(String sourceId) {
int source = nodeIdToIndex.get(sourceId);
int[] distances = DijkstraOptimized.dijkstra(graph, source);
Map<String, Integer> result = new HashMap<>();
for (int i = 0; i < distances.length; i++) {
result.put(nodes.get(i).id, distances[i]);
}
return result;
}
}
}
|
6.2 社交网络分析#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| public class SocialNetworkAnalyzer {
/**
* 社交网络中的影响力传播分析
*/
public static class InfluenceAnalyzer {
private List<List<Edge>> network;
private Map<Integer, String> userNames;
public InfluenceAnalyzer(Map<Integer, String> users,
Map<Integer, Map<Integer, Integer>> connections) {
this.userNames = users;
buildInfluenceGraph(users.size(), connections);
}
private void buildInfluenceGraph(int userCount,
Map<Integer, Map<Integer, Integer>> connections) {
network = new ArrayList<>();
for (int i = 0; i < userCount; i++) {
network.add(new ArrayList<>());
}
for (Map.Entry<Integer, Map<Integer, Integer>> entry : connections.entrySet()) {
int from = entry.getKey();
for (Map.Entry<Integer, Integer> connection : entry.getValue().entrySet()) {
int to = connection.getKey();
int influence = connection.getValue();
// 影响力作为边权重（值越小影响力越大）
network.get(from).add(new Edge(to, 100 - influence));
}
}
}
/**
* 计算用户的影响力覆盖范围
*/
public Map<String, Integer> calculateInfluenceReach(int userId, int maxDistance) {
int[] distances = DijkstraOptimized.dijkstra(network, userId);
Map<String, Integer> reachableUsers = new HashMap<>();
for (int i = 0; i < distances.length; i++) {
if (i != userId && distances[i] <= maxDistance && distances[i] != Integer.MAX_VALUE) {
reachableUsers.put(userNames.get(i), distances[i]);
}
}
return reachableUsers;
}
/**
* 找到两个用户之间的最短社交路径
*/
public List<String> findSocialPath(int fromUser, int toUser) {
List<Integer> path = DijkstraOptimized.getShortestPath(network, fromUser, toUser);
return path.stream()
.map(userNames::get)
.collect(Collectors.toList());
}
}
}
|
7. 算法的局限性和替代方案#
7.1 负权边问题#
Dijkstra算法的一个重要局限是无法处理负权边。当图中存在负权边时，算法可能产生错误的结果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| public class NegativeWeightExample {
/**
* 演示Dijkstra算法在负权边情况下的问题
*/
public static void demonstrateNegativeWeightProblem() {
// 构建一个包含负权边的图
/*
* 图结构：
* 0 ---(1)---> 1
* | |
* |(-10) |(5)
* v v
* 2 ---(1)---> 3
*/
List<List<Edge>> graph = Arrays.asList(
Arrays.asList(new Edge(1, 1), new Edge(2, -10)),
Arrays.asList(new Edge(3, 5)),
Arrays.asList(new Edge(3, 1)),
new ArrayList<>()
);
System.out.println("=== 负权边问题演示 ===");
System.out.println("图中包含负权边：0->2权重为-10");
int[] result = DijkstraOptimized.dijkstra(graph, 0);
System.out.println("Dijkstra结果: " + Arrays.toString(result));
System.out.println("从0到3的路径：0->2->3，实际最短距离应为-9");
System.out.println("但Dijkstra可能给出错误结果");
}
}
|
7.2 Bellman-Ford算法#
对于包含负权边的图，应该使用Bellman-Ford算法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| public class BellmanFordAlgorithm {
static class GraphEdge {
int from, to, weight;
GraphEdge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
/**
* Bellman-Ford算法实现
* @param edges 图的所有边
* @param vertexCount 顶点数量
* @param src 源点
* @return 距离数组，如果存在负权回路返回null
*/
public static int[] bellmanFord(List<GraphEdge> edges, int vertexCount, int src) {
int[] dist = new int[vertexCount];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// 进行V-1次松弛操作
for (int i = 0; i < vertexCount - 1; i++) {
for (GraphEdge edge : edges) {
if (dist[edge.from] != Integer.MAX_VALUE &&
dist[edge.from] + edge.weight < dist[edge.to]) {
dist[edge.to] = dist[edge.from] + edge.weight;
}
}
}
// 检查负权回路
for (GraphEdge edge : edges) {
if (dist[edge.from] != Integer.MAX_VALUE &&
dist[edge.from] + edge.weight < dist[edge.to]) {
System.out.println("图中存在负权回路！");
return null;
}
}
return dist;
}
/**
* 比较Dijkstra和Bellman-Ford的性能
*/
public static void performanceComparison() {
System.out.println("=== 算法性能比较 ===");
System.out.println("Dijkstra算法:");
System.out.println("- 时间复杂度: O((V+E)logV) 使用优先队列");
System.out.println("- 空间复杂度: O(V)");
System.out.println("- 适用场景: 非负权图的单源最短路径");
System.out.println();
System.out.println("Bellman-Ford算法:");
System.out.println("- 时间复杂度: O(VE)");
System.out.println("- 空间复杂度: O(V)");
System.out.println("- 适用场景: 可能包含负权边的图，能检测负权回路");
System.out.println();
System.out.println("选择建议:");
System.out.println("- 对于非负权图：优先选择Dijkstra算法");
System.out.println("- 对于可能有负权边的图：使用Bellman-Ford算法");
System.out.println("- 对于多源最短路径：考虑Floyd-Warshall算法");
}
}
|
7.3 Floyd-Warshall算法#
对于全对最短路径问题，Floyd-Warshall算法是更好的选择：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| public class FloydWarshall {
/**
* Floyd-Warshall算法实现
* @param graph 邻接矩阵，INF表示无直接边
* @return 所有顶点对之间的最短距离矩阵
*/
public static int[][] floydWarshall(int[][] graph) {
int n = graph.length;
int[][] dist = new int[n][n];
// 初始化距离矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = graph[i][j];
}
}
// 三重循环：k为中间顶点
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != Integer.MAX_VALUE &&
dist[k][j] != Integer.MAX_VALUE &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
/**
* 算法选择指南
*/
public static void algorithmSelectionGuide() {
System.out.println("=== 最短路径算法选择指南 ===");
System.out.println();
System.out.println("1. 单源最短路径（从一个点到所有其他点）:");
System.out.println(" - 非负权图: Dijkstra算法 O((V+E)logV)");
System.out.println(" - 可能有负权边: Bellman-Ford算法 O(VE)");
System.out.println();
System.out.println("2. 单对最短路径（两个特定点之间）:");
System.out.println(" - 小图: 直接使用Dijkstra");
System.out.println(" - 大图: 双向搜索或A*算法");
System.out.println();
System.out.println("3. 全对最短路径（所有点对之间）:");
System.out.println(" - 稠密图: Floyd-Warshall算法 O(V³)");
System.out.println(" - 稀疏图: 对每个顶点运行Dijkstra O(V(V+E)logV)");
System.out.println();
System.out.println("4. 特殊情况:");
System.out.println(" - DAG(有向无环图): 拓扑排序+动态规划 O(V+E)");
System.out.println(" - 树结构: DFS/BFS O(V)");
System.out.println(" - 网格图: A*算法配合曼哈顿距离启发函数");
}
}
|
8. 性能分析和优化建议#
8.1 时间复杂度分析#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
| public class PerformanceAnalysis {
/**
* 不同实现方式的时间复杂度对比
*/
public static void analyzeTimeComplexity() {
System.out.println("=== Dijkstra算法时间复杂度分析 ===");
System.out.println();
System.out.println("1. 基础实现（邻接矩阵 + 线性搜索）:");
System.out.println(" - 找最小距离顶点: O(V)");
System.out.println(" - 重复V次: O(V²)");
System.out.println(" - 松弛操作: O(V²)");
System.out.println(" - 总时间复杂度: O(V²)");
System.out.println();
System.out.println("2. 优先队列实现（邻接表 + 二叉堆）:");
System.out.println(" - 每个顶点最多入队一次: O(V)");
System.out.println(" - 每条边最多松弛一次: O(E)");
System.out.println(" - 堆操作: O(logV)");
System.out.println(" - 总时间复杂度: O((V+E)logV)");
System.out.println();
System.out.println("3. 斐波那契堆实现:");
System.out.println(" - 减少关键字操作: O(1)摊销");
System.out.println(" - 总时间复杂度: O(VlogV + E)");
System.out.println();
System.out.println("选择建议:");
System.out.println("- 稠密图(E ≈ V²): 基础实现更高效");
System.out.println("- 稀疏图(E << V²): 优先队列实现更高效");
System.out.println("- 极大规模图: 考虑斐波那契堆实现");
}
/**
* 实际性能测试
*/
public static void performanceBenchmark() {
System.out.println("=== 性能测试 ===");
// 生成测试图
int[] graphSizes = {100, 500, 1000, 5000};
for (int size : graphSizes) {
List<List<Edge>> denseGraph = generateDenseGraph(size);
List<List<Edge>> sparseGraph = generateSparseGraph(size);
System.out.println("图规模: " + size + " 个顶点");
// 测试稠密图
long startTime = System.nanoTime();
DijkstraOptimized.dijkstra(denseGraph, 0);
long denseTime = System.nanoTime() - startTime;
// 测试稀疏图
startTime = System.nanoTime();
DijkstraOptimized.dijkstra(sparseGraph, 0);
long sparseTime = System.nanoTime() - startTime;
System.out.println(" 稠密图用时: " + denseTime / 1_000_000 + " ms");
System.out.println(" 稀疏图用时: " + sparseTime / 1_000_000 + " ms");
System.out.println();
}
}
private static List<List<Edge>> generateDenseGraph(int size) {
// 生成稠密图（边数接近V²）
List<List<Edge>> graph = new ArrayList<>();
Random random = new Random(42);
for (int i = 0; i < size; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i != j && random.nextDouble() < 0.8) { // 80%的边密度
graph.get(i).add(new Edge(j, random.nextInt(100) + 1));
}
}
}
return graph;
}
private static List<List<Edge>> generateSparseGraph(int size) {
// 生成稀疏图（边数约为2V）
List<List<Edge>> graph = new ArrayList<>();
Random random = new Random(42);
for (int i = 0; i < size; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < size; i++) {
// 每个顶点平均连接2个其他顶点
for (int j = 0; j < 2; j++) {
int target = random.nextInt(size);
if (target != i) {
graph.get(i).add(new Edge(target, random.nextInt(100) + 1));
}
}
}
return graph;
}
}
|
8.2 内存优化技巧#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
| public class MemoryOptimization {
/**
* 内存优化的Dijkstra实现
*/
public static class MemoryEfficientDijkstra {
// 使用位运算来压缩布尔数组
static class BitSet {
private long[] bits;
private int size;
public BitSet(int size) {
this.size = size;
this.bits = new long[(size + 63) / 64];
}
public void set(int index) {
bits[index / 64] |= (1L << (index % 64));
}
public boolean get(int index) {
return (bits[index / 64] & (1L << (index % 64))) != 0;
}
}
/**
* 内存优化版本的Dijkstra算法
*/
public static int[] memoryEfficientDijkstra(List<List<Edge>> graph, int src) {
int n = graph.size();
int[] dist = new int[n];
BitSet visited = new BitSet(n); // 使用位图代替布尔数组
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// 使用自定义的优先队列，减少对象创建
IntPriorityQueue pq = new IntPriorityQueue(n);
pq.offer(src, 0);
while (!pq.isEmpty()) {
int u = pq.poll();
if (visited.get(u)) continue;
visited.set(u);
for (Edge edge : graph.get(u)) {
int v = edge.to;
int weight = edge.weight;
if (!visited.get(v) && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.offer(v, dist[v]);
}
}
}
return dist;
}
/**
* 自定义的整数优先队列，避免装箱拆箱
*/
static class IntPriorityQueue {
private int[] vertices;
private int[] priorities;
private int size;
public IntPriorityQueue(int capacity) {
vertices = new int[capacity];
priorities = new int[capacity];
size = 0;
}
public void offer(int vertex, int priority) {
vertices[size] = vertex;
priorities[size] = priority;
heapifyUp(size);
size++;
}
public int poll() {
int result = vertices[0];
size--;
vertices[0] = vertices[size];
priorities[0] = priorities[size];
heapifyDown(0);
return result;
}
public boolean isEmpty() {
return size == 0;
}
private void heapifyUp(int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (priorities[index] >= priorities[parent]) break;
swap(index, parent);
index = parent;
}
}
private void heapifyDown(int index) {
while (true) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < size && priorities[left] < priorities[smallest]) {
smallest = left;
}
if (right < size && priorities[right] < priorities[smallest]) {
smallest = right;
}
if (smallest == index) break;
swap(index, smallest);
index = smallest;
}
}
private void swap(int i, int j) {
int tempV = vertices[i];
int tempP = priorities[i];
vertices[i] = vertices[j];
priorities[i] = priorities[j];
vertices[j] = tempV;
priorities[j] = tempP;
}
}
}
}
|
9. 总结#
Dijkstra算法作为图论中最重要的算法之一，具有广泛的应用价值和深远的影响。通过本文的详细介绍，我们可以总结出以下要点：
9.1 算法优势#
- 高效性: 对于非负权图，提供了最优的单源最短路径解决方案
- 实用性: 在现实世界中有大量应用，从GPS导航到网络路由
- 可优化: 通过不同的数据结构可以适应不同规模的问题
9.2 关键要点#
- 正确性: 基于贪心策略，在非负权图上保证找到最优解
- 复杂度: 时间复杂度从O(V²)到O((V+E)logV)不等，取决于实现方式
- 局限性: 无法处理负权边，需要使用其他算法如Bellman-Ford
9.3 实践建议#
- 选择合适的实现: 根据图的密度选择邻接矩阵或邻接表表示
- 考虑优化: 对于特定应用场景，可以考虑双向搜索、A*等优化
- 理解局限: 明确算法的适用范围，避免在不合适的场景下使用
9.4 学习价值#
学习Dijkstra算法不仅能帮助我们解决实际的最短路径问题，更重要的是能够培养我们的算法思维：
- 贪心策略的运用
- 图论问题的建模能力
- 复杂度分析的技能
- 数据结构选择的考量
通过深入理解和实践Dijkstra算法，我们能够更好地应对复杂的计算问题，为今后学习更高级的图算法奠定坚实的基础。无论是在学术研究还是工程实践中，这个经典算法都将继续发挥其重要作用。
希望本文能够帮助读者全面掌握Dijkstra算法，并在实际项目中灵活运用。记住，算法学习的关键在于理解其思想精髓，然后通过大量的练习来巩固和提升。