当前位置：首页 > news >正文

Dijkstra算法

news 2026/3/26 22:43:57

一、算法核心定义与适用场景

Dijkstra算法是一种基于贪心策略的图算法，专门用于解决单源最短路径问题（Single Source Shortest Path, SSSP），即给定一个带权图G=(V, E)（其中V为顶点集合，E为边集合）和一个指定源顶点s，求解从s到图中所有其他顶点的最短路径长度。

该算法的适用前提有两个关键约束：一是图中所有边的权重必须为非负值；二是图可以是有向图或无向图（无向图可视为每条边双向存在的有向图）。若图中存在负权边，Dijkstra算法将失效，此时需采用Bellman-Ford算法或SPFA算法等替代方案；而与Floyd-Warshall算法（解决任意两点最短路径）相比，Dijkstra算法在单源场景下具有更高的时间效率，尤其在稀疏图中表现更为优异。

其典型应用场景涵盖多个领域：

地图导航：GPS导航系统中，用于计算两点之间的最短行驶路径、最少耗时路径或最低油耗路径；
通信网络：计算机网络中，用于路由选择，寻找数据包传输的最短延迟路径，提升通信效率；
运筹优化：物流与运输领域，选择货物运输的最低成本路线，降低物流开销；
人工智能：机器人寻路、图搜索等场景中，用于路径规划，引导智能体高效到达目标位置。

二、算法核心原理与执行步骤

Dijkstra算法的核心思想是“由近及远、层层扩展”的贪心策略：从源顶点出发，每次选择当前距离源顶点最近且未被处理的顶点，确定其最短路径长度，再以该顶点为中介，更新其邻接顶点到源顶点的距离，重复此过程，直至所有顶点均被处理完毕。

算法执行过程需维护两个关键数据结构：

距离数组dist[]：用于存储源顶点s到图中每个顶点v的当前最短距离，初始时dist[s] = 0（源顶点到自身距离为0），其余顶点的dist值均设为无穷大（表示初始状态下未发现可达路径）；
访问标记数组visited[]：用于标记顶点是否已确定最短路径，初始时所有顶点均为未访问状态（visited[v] = false），源顶点处理完成后标记为已访问（visited[s] = true）。

具体执行步骤（以有向正权图为例）

假设图G包含顶点A、B、C、D、E，源顶点为A，各边权重如图所示（A→B权重10，A→C权重3，A→D权重20，C→B权重2，C→E权重15，B→D权重5，D→E权重11），执行步骤如下：

步骤1：初始化

dist数组初始值：dist[A] = 0，dist[B] = ∞，dist[C] = ∞，dist[D] = ∞，dist[E] = ∞；visited数组所有元素均为false。

步骤2：第一次迭代

从未访问顶点中选择dist值最小的顶点，即源顶点A（dist[A] = 0），标记A为已访问（visited[A] = true）。遍历A的所有邻接顶点（B、C、D），更新其dist值：

dist[B] = min(∞, dist[A] + 10) = 10；
dist[C] = min(∞, dist[A] + 3) = 3；
dist[D] = min(∞, dist[A] + 20) = 20。

步骤3：第二次迭代

从未访问顶点（B、C、D、E）中选择dist值最小的顶点C（dist[C] = 3），标记C为已访问。遍历C的所有邻接顶点（B、E），更新其dist值：

dist[B] = min(10, dist[C] + 2) = 5；
dist[E] = min(∞, dist[C] + 15) = 18。

步骤4：第三次迭代

从未访问顶点（B、D、E）中选择dist值最小的顶点B（dist[B] = 5），标记B为已访问。遍历B的邻接顶点D，更新其dist值：

dist[D] = min(20, dist[B] + 5) = 10。

步骤5：第四次迭代

从未访问顶点（D、E）中选择dist值最小的顶点D（dist[D] = 10），标记D为已访问。遍历D的邻接顶点E，更新其dist值：

dist[E] = min(18, dist[D] + 11) = 18（无需更新）。

步骤6：第五次迭代

仅剩未访问顶点E（dist[E] = 18），标记E为已访问。E无未访问的邻接顶点，无需更新dist值。

步骤7：算法终止

所有顶点均已访问，dist数组最终值即为源顶点A到各顶点的最短路径长度：A→A（0）、A→C→B（5）、A→C（3）、A→C→B→D（10）、A→C→E（18）。

从上述步骤可看出，Dijkstra算法的核心特性的是：一旦某个顶点被标记为已访问，其dist值将永久确定，不再被后续迭代更新，这也是贪心策略在算法中的核心体现。

三、算法实现方式（以Java为例）

Dijkstra算法的实现有两种常见方式，分别基于邻接矩阵和邻接表，两种方式在时间复杂度和空间复杂度上各有优劣，适用于不同规模的图场景。

1. 基于邻接矩阵的实现

邻接矩阵适用于顶点数量较少（如n<1000）的稠密图，其空间复杂度为O(n²)，时间复杂度为O(n²)（n为顶点数量）。核心逻辑是通过双重循环，依次找到未访问顶点中的最小dist值顶点，并更新邻接顶点的距离。

import java.util.Arrays; public class DijkstraMatrix { // 无穷大表示不可达 private static final int INF = Integer.MAX_VALUE / 2; public static int[] dijkstra(int[][] graph, int source) { int n = graph.length; // 距离数组：存储源顶点到各顶点的最短距离 int[] dist = new int[n]; // 访问标记数组：标记顶点是否已确定最短路径 boolean[] visited = new boolean[n]; // 初始化距离数组和访问标记数组 Arrays.fill(dist, INF); dist[source] = 0; // 迭代n-1次（除源顶点外，共n-1个顶点需处理） for (int i = 0; i < n - 1; i++) { // 步骤1：找到未访问顶点中dist值最小的顶点u int u = findMinDistVertex(dist, visited); // 标记u为已访问 visited[u] = true; // 步骤2：更新u的所有邻接顶点的dist值 for (int v = 0; v < n; v++) { // 条件：v未访问、u到v可达、经过u到v的路径更短 if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) { dist[v] = dist[u] + graph[u][v]; } } } return dist; } // 找到未访问顶点中dist值最小的顶点 private static int findMinDistVertex(int[] dist, boolean[] visited) { int minDist = INF; int minIndex = -1; for (int i = 0; i < dist.length; i++) { if (!visited[i] && dist[i] < minDist) { minDist = dist[i]; minIndex = i; } } return minIndex; } // 测试示例 public static void main(String[] args) { // 邻接矩阵表示图，INF表示不可达 int[][] graph = { {0, 10, 3, 20, INF}, {INF, 0, INF, 5, INF}, {INF, 2, 0, INF, 15}, {INF, INF, INF, 0, 11}, {INF, INF, INF, INF, 0} }; int source = 0; // 源顶点为A（索引0） int[] result = dijkstra(graph, source); // 输出结果 System.out.println("源顶点到各顶点的最短路径长度："); for (int i = 0; i < result.length; i++) { System.out.println("A -> " + (char) ('A' + i) + "：" + (result[i] == INF ? "不可达" : result[i])); } } }

2. 基于邻接表与优先队列的优化实现

对于顶点数量较多的稀疏图，邻接矩阵的空间利用率极低，此时可采用邻接表存储图结构，并结合优先队列（最小堆）优化“寻找最小dist值顶点”的过程，将时间复杂度优化至O(MlogN)（M为边的数量，N为顶点数量），这也是工程实践中最常用的实现方式。

核心优化点：利用优先队列快速获取当前dist值最小的顶点，避免双重循环遍历，大幅提升算法效率；邻接表仅存储存在的边，降低空间开销。

四、算法优化方向与局限性

1. 常见优化方向

优先队列优化：采用斐波那契堆替代普通最小堆，可将时间复杂度进一步优化至O(M + NlogN)，但斐波那契堆实现复杂，工程中应用较少，普通场景下优先队列已能满足需求；
路径记录优化：在原有基础上增加前驱顶点数组prev[]，记录每个顶点的最短路径前驱，可回溯出具体的最短路径（而非仅获取路径长度）；
稀疏图适配：结合邻接表存储，减少无效空间占用，尤其适用于顶点数量庞大的场景（如百万级顶点的地图导航）。