【数据结构】图论经典：Dijkstra最短路径算法精解与工程优化

(最短路径)

导读

大家好，很高兴又和大家见面啦！！！

在探索图论中的最短路径问题时，我们面对两个核心场景：

• 单源最短路径（从一个起点到所有其他点的最短距离）
• 各顶点间最短路径（计算图中任意两点的最短距离）

在上一篇中，我们学会了用广度优先搜索（BFS） 解决无权图的最短路径。但BFS面对现实世界的带权场景时（如公路导航、网络路由），暴露了根本性不足：

• 无法处理变权差异：机械追求"最少边数"，忽略关键的距离、成本等权值因素
• 分层遍历局限：严格按层级扩展，常错过边数稍多但总权值更小的优质路径

如何突破BFS的限制？

图灵奖得主Edsger Dijkstra给出了划时代答案：

🔑 Dijkstra算法——专为边权非负的带权图设计的单源最短路径解决方案 🚀 它通过动态更新路径估值、优先探索当前最优节点、支持跨层级修正等创新机制

接下来您将深入探索：

• Dijkstra与Prim算法的数学共性（1.2节）
• 图解5顶点带权图的精妙推演过程（1.3节）
• 三大核心数组（visited/dist/path）的工作原理（1.4节）
• 时间复杂度优化秘技（1.5节）

计算机科学的瑰宝之门已开启，滚动鼠标开启这段智性之旅吧！

一、Dijkstra算法

1.1 算法由来

Dijkstra（迪杰斯特拉）算法是由Edsger·Wybe·Dijkstra（艾兹格·W·迪杰斯特拉）提出。

Edsger·Wybe·Dijkstra 的主要成就如下所示：

• 1972年图灵奖得主
• 提出"goto有害理论"——操作系统，虚拟存储技术
• 发明了信号量机制PV原语——操作系统，进程同步
• 提出了银行家算法——操作系统，死锁
• 解决了哲学家进餐问题——操作系统，死锁 提出了Dijkstra最短路径算法——数据结构

1.2 基本原理

Dijkstra 算法用于解决边权非负带权图的单源最短路径问题，其基本原理是：

• 从源点开始，每次选择与源点的带权路径长度最小的且未处理的顶点加入到路径中

Dijkstra 算法与前面介绍的最小生成树的Prim算法有异曲同工之妙：

• 同样都是以顶点为核心：
  • Prim算法以顶点为驱动，逐步向外扩展，依次选择最小权值边，逐步构建最小生成树
  • Dijkstra算法以顶点为驱动，逐步向外查找，依次选择与源点的带权路径长度最小的顶点，逐步构建最短路径树

虽然二者相似，但是还是存在本质上的差异：

• 算法的适用对象不同：
  • Prim算法适用于带权连通无向图
  • Dijkstra算法适用于边权非负的带权图；
• 算法的核心目标不同：
  • Prim算法用于解决连通性问题
  • Dijkstra算法用于解决路径问题

这里我们以带权有向图G为例来演示一下整个算法的执行过程：

graph LR
a--10-->b--1-->c--4-->d--7-->a
b--2-->e--2-->d--6-->e
e--3-->b
a--5-->e--9-->c

在该带权有向图中有5个顶点与10条弧：

• |V| = {a, b, c, d, e}
• |E| = {\<a, b, 10>, <a, e, 5>, \<b, c, 1>, <b, e, 2>, \<c, d, 4>, \<d, c, 6>, <d, a, 7>, \<e, b, 3>, <e, c, 9>, <e, d, 2> \ }

这里我们以点a作为路径源点，下面就是通过Dijkstra 算法获取源点到其他顶点的最短路径的过程：

• 从源点a出发，依附于顶点a的有两条弧： 弧 <a, b, 10><a, e, 5><a, b, 10><a, e, 5>

graph LR
a--5-->e

• 我们接着从顶点e出发，依附与顶点e的有3条弧，依附于顶点a的有一条弧 弧 <a, b, 10><e, b, 3><e, c, 9><e, d, 2><a, b, 10><a, e, b, 5 + 3><a, e, c, 5 + 9><a, e, d, 5 + 2>

graph LR
a--5-->e--2-->d

• 接着我们从顶点d出发，依附于顶点d的有两条弧，依附于顶点a的有一条弧，依附于顶点e的有两条弧： 弧 <a, b, 10><e, b, 3><e, c, 9><d, c, 6><d, a, 7><a, b, 10><a, e, b, 5 + 3><a, e, c, 5 + 9><a, e, d, c, 7 + 6><a, e, d, a, 7 + 7>

graph LR
a--5-->e--3-->b

• 下面我们继续从顶点b出发，依附于顶点b的有两条弧，依附于顶点e的有一条弧，依附于顶点d的有2条弧： 弧 <e, c, 9><d, c, 6><d, a, 7><b, c, 1><b, e, 2><a, e, c, 5 + 9><a, e, d, c, 7 + 6><a, e, d, a, 7 + 7><a, e, b, c, 8 + 1><a, e, b, e, 8 +2>

graph LR
a--5-->e--3-->b--1-->c

现在我们就找到了从源点a出发到各个顶点的最短路径长度，

1.3 算法逻辑

从前面的演示过程我们可以看到，Dijkstra算法在执行时，实际上就是从顶点出发，依次找到连通其他顶点的最小带权路径长度；

这里就会存在一个问题：当图中存在环时，即使我们以经找到了源点到该顶点的最短路径，在后续的查找过程中，我们依旧会找到多条从源点到某个顶点的带权路径，如：

• <a, e, d, a, 7 + 7>
• <a, e, b, e, 8 +2>

显然这两条路径是无用的，为了过滤掉这种情况的发生，我们还需要对已经找到最短路径的顶点进行标记，以确保每次查找的顶点都是还未找到最短路径的顶点；

为了能够准确的反映每一条带权路径，我们还可以选择记录当前顶点的前驱顶点，以便在查询最短路径时能够准确的找到从源点开始到各顶点的最短路径；

因此在Dijkstra算法中我们需要维护3个数组：

• visited[] 用于标记当前顶点是否找到了最短路径
• d[] 用于记录从源点到当前顶点的带权路径长度
• path[] 用于记录当前顶点的前驱顶点

在理解了上述问题后，下面我们就来整理以下Dijkstra算法的整体逻辑：

• 初始化：假设从源点 v_0 出发，依次获取 v_0 到 v_i 的最短路径 初始化源点的visited[]、d[]、path[]中的初始值 visited[v_0] = true ：源点已经找到了从源点到源点的最短路径 d[v_0] = 0 ：从源点到源点的最短路径长度为0 path[v_0] = -1：该最短路径中，源点不存在前驱顶点 从源点出发，依次记录源点到各顶点的带权路径长度 源点与顶点之间存在路径，则带权路径长度为依附于源点与该顶点的弧的权值 源点与顶点之间不存在路径，则带权路径长度为 \infty 从源点出发，依次记录源点到各顶点的带权路径长度中各顶点的前驱顶点 源点与顶点之间存在路径，则该顶点的前驱顶点为源点 源点与顶点之间不存在路径，则该顶点的前驱顶点为 -1
• 从visited[]中选择某个顶点 v_i，且该顶点满足： visited[v_i] = false ：当前顶点还未找到最短路径 d[v_i] = min(dist) ：当前顶点的带权路径长度最小 修改该顶点 v_i 的状态： visited[v_i] = true ：当前顶点找到了最短路径
• 从当前顶点v_i出发记录源点到各顶点的带权路径长度 d[v_i] + v_j->info < d[v_i]v_j的前驱顶点
• 重复2~3步操作，直到所有顶点都找到了最短路径

该算法的C语言代码如下所示：

bool visited[MAXVERSIZE];		// 顶点访问标记数组
int dist[MAXVERSIZE];			// 最短路径长度数组
int path[MAXVERSIZE];			// 顶点前驱顶点数组
void Dijkstra(graph* g, int v){
	// 初始化
	for (int i = 0; i < MAXVERSIZE; i++) {
		// 初始化源点
		if (i == v) {
			visited[i] = true;
			dist[i] = 0;
			path[i] = -1;
		}
		// 初始化其他顶点
		else {
			visited[i] = false;
			// 源点与该顶点之间存在路径
			if (Connect(g, v, i)) {
				dist[i] = Get_edge_value(g, v, i);
				path[i] = v;
			}
			// 源点与该顶点之间不存在路径
			else {
				dist[i] = INT_MAX;
				path[i] = -1;
			}
		}
	}
	// 获取最短路径
	while (1) {
		int begin = -1;				// 记录路径起点
		int min_list = INT_MAX;		// 记录当前查找的最短路径
		for (int i = 0; i < MAXVERSIZE; i++) {
			// 当前顶点未找到最短路径，且当前路径小于当前最短路径
			if (!visited[i] && dist[i] < min_list) {
				min_list = dist[i];	// 修改当前最短路径
				begin = i;			// 修改当前路径起点
			}
		}
		// 当图中剩余结点均不联通，则无需继续查找
		if (begin == -1) {
			break;
		}
		// 修改最短路径的顶点begin状态
		visited[begin] = true;
		// 从当前起点出发，更新当前起点到其它顶点之间的路径长度与前驱顶点
		for (int j = 0; j < MAXVERSIZE; j++) {
			if (!visited[j] && Connect(g, begin, j)) {
				int info = Get_edge_value(g, begin, j);		// 获取起点到当前顶点的权值
				// 松弛操作
				if (dist[begin] + info < dist[j]) {			// 新的路径长度小于当前顶点的路径长度
					dist[j] = dist[begin] + info;			// 更新当前顶点的路径长度
					path[j] = begin;						// 更新当前顶点的前驱顶点
				}
			}
		}
	}
}

1.4 算法评价

此时我们就实现了Dijkstra算法，在当前的实现逻辑中，算法的时间复杂度为：O(|V|^2)

其主要的时间消耗在以下几个部分：

• 初始化部分，需要遍历图中的所有顶点——O(|V|)
• 第一轮获取最短路径 查找最小带权路径长度——O(|V|) 通过松弛操作更新邻居的最小带权路径长度——O(|V|)
• 最坏情况下：图为强连通图（有向图）或连通图（无向图），那么循环需要执行|V| - 1 次，每一次都能确定一个顶点的最短路径
• 最好情况下：所选源点与其他顶点间均不存在路径，那么循环只会执行一次

因此该算法实现的时间复杂度为： - 最好情况：T(N) = O(|V|) + O(|V|) + O(|V|) = O(|V|) - 最坏情况：T(N) = O(|V|) + O(|V|)×[O(|V|)+O(|V|)] = O(|V|^2)

那我们有没有办法进一步优化呢？

1.5 算法优化

可以看到，在最坏的情况下，对时间复杂度影响最大的就是在查找最短路径的部分：

• 外层循环的循环次数由图的顶点数决定，这是我们无法优化的
• 内存循环的循环次数有两个决定因素：
  • 查找新起点：由查找效率决定，这里可以进行优化
  • 更新邻居：由查找邻接点的效率决定，这里可以进行优化

1.5.1 查找新起点优化

在现在的实现中，我们是采用的顺序查找的方式，顺序遍历顶点，那我们设想一下，如果我们能够优化查找的话，是不是就能提高整体的算法效率了呢？

这里我们推荐最小堆来优化查找的时间复杂度，简单的理解就是将顶点按照路径长度从小到大进行排列，我们每次在选择新的起点时，只需要选择堆顶元素即可。

当然，这里涉及到堆排序的算法实现，相关内容我们会在后面的篇章中进一步分享。

1.5.2 更新邻居优化

如果我们在查找到新的起点后，能够根据该起点快速的找到其邻接点，那么我们是不是还能够进一步优化算法呢？

既然这样，我们不妨采用将遍历顶点改为遍历边——即采用邻接表的方式来查找新起点的邻接点，来达到进一步优化更新邻居的效率：

		// 更新邻居优化
		for (int p = FirstNeighbor(g, begin); p >= 0; p = NextNeighbor(g, begin, p)) {
			if (!visited[p]) {
				int info = Get_edge_value(g, begin, p);		// 获取起点到当前顶点的权值
				// 松弛操作
				if (dist[begin] + info < dist[p]) {			// 新的路径长度小于当前顶点的路径长度
					dist[p] = dist[begin] + info;			// 更新当前顶点的路径长度
					path[p] = begin;						// 更新当前顶点的前驱顶点
				}
			}
		}

在这种优化下，我们将原先的更新邻居时每一趟都需要遍历全部顶点使得时间复杂度为O(|V|)降低到了仅需遍历该顶点的邻居O(deg(begin))。算法中更新邻居的整体时间复杂度也从 O(|V|^2) 降低到了 O(|E|)；

当然，这种优化的前提是该图为边少顶点多的稀疏图，而对于边多，顶点少的稠密图而言，我们还是采用遍历顶点的方式会更为合适。

结语：图论智慧的下一站

通过本篇的探索，我们共同破解了最短路径问题中的关键一环——掌握了Dijkstra算法这一图论瑰宝。让我们回顾核心收获：

知识精华回顾

• 破局之作 Dijkstra算法完美解决了BFS在带权图中的局限，通过：
  • 动态维护dist/path/visited三核心数组
  • 优先扩展当前最短路径顶点（贪心策略）
  • 支持跨层级路径修正（松弛操作）
• 效率革命 从基础实现的O(|V|^2)到堆优化+邻接表的O( |E|log|V|)，展现了算法优化的精妙思路：

      graph LR
   时间复杂度优化-->堆优化查找顶点
   时间复杂度优化-->邻接表加速邻居访问

• 跨界共鸣 揭示Dijkstra与Prim算法的神似形异：
  • 同是顶点驱动的贪心策略
  • 异在目标函数（路径长度 vs 边权总和）
  • 应用场景分野（有向/无向图 vs 连通无向图）

下一站预告：Floyd的全局智慧

当我们解决了单源最短路径问题，自然面临更宏大的挑战：

如何同时求解所有顶点对之间的最短路径？

这正是下一篇的主角——Floyd算法的舞台！该算法将展现： 🔥 三重循环的魔力：用简洁的迭代征服全图路径 🌉 负权边处理能力：突破Dijkstra的边界 📊 动态规划之美：用子问题拼接全局最优解

想象一下：输入邻接矩阵，输出任意两城市的最短里程表——这就是Floyd的威力！