一、算法核心定义与适用场景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权重10A→C权重3A→D权重20C→B权重2C→E权重15B→D权重5D→E权重11执行步骤如下步骤1初始化dist数组初始值dist[A] 0dist[B] ∞dist[C] ∞dist[D] ∞dist[E] ∞visited数组所有元素均为false。步骤2第一次迭代从未访问顶点中选择dist值最小的顶点即源顶点Adist[A] 0标记A为已访问visited[A] true。遍历A的所有邻接顶点B、C、D更新其dist值dist[B] min(∞, dist[A] 10) 10dist[C] min(∞, dist[A] 3) 3dist[D] min(∞, dist[A] 20) 20。步骤3第二次迭代从未访问顶点B、C、D、E中选择dist值最小的顶点Cdist[C] 3标记C为已访问。遍历C的所有邻接顶点B、E更新其dist值dist[B] min(10, dist[C] 2) 5dist[E] min(∞, dist[C] 15) 18。步骤4第三次迭代从未访问顶点B、D、E中选择dist值最小的顶点Bdist[B] 5标记B为已访问。遍历B的邻接顶点D更新其dist值dist[D] min(20, dist[B] 5) 10。步骤5第四次迭代从未访问顶点D、E中选择dist值最小的顶点Ddist[D] 10标记D为已访问。遍历D的邻接顶点E更新其dist值dist[E] min(18, dist[D] 11) 18无需更新。步骤6第五次迭代仅剩未访问顶点Edist[E] 18标记E为已访问。E无未访问的邻接顶点无需更新dist值。步骤7算法终止所有顶点均已访问dist数组最终值即为源顶点A到各顶点的最短路径长度A→A0、A→C→B5、A→C3、A→C→B→D10、A→C→E18。从上述步骤可看出Dijkstra算法的核心特性的是一旦某个顶点被标记为已访问其dist值将永久确定不再被后续迭代更新这也是贪心策略在算法中的核心体现。三、算法实现方式以Java为例Dijkstra算法的实现有两种常见方式分别基于邻接矩阵和邻接表两种方式在时间复杂度和空间复杂度上各有优劣适用于不同规模的图场景。1. 基于邻接矩阵的实现邻接矩阵适用于顶点数量较少如n1000的稠密图其空间复杂度为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[]记录每个顶点的最短路径前驱可回溯出具体的最短路径而非仅获取路径长度稀疏图适配结合邻接表存储减少无效空间占用尤其适用于顶点数量庞大的场景如百万级顶点的地图导航。2. 算法局限性不支持负权边若图中存在负权边贪心策略将失效可能导致已标记为“已访问”的顶点其dist值可通过负权边被进一步减小不支持负权回路负权回路会导致路径长度无限减小算法无法终止单源场景限制仅能求解从单个源顶点到其他顶点的最短路径若需求解任意两点之间的最短路径需多次调用算法或采用Floyd-Warshall算法。