Dijkstra算法：单源最短路的贪心经典，稠密/稀疏图全解

在图论的最短路问题中，单源最短路径（求一个起点到图中所有其他节点的最短距离）是最核心的场景之一。而Dijkstra算法就是解决这个问题的「王牌算法」，它基于贪心思想，仅适用于边权非负的图，凭借简洁的逻辑和高效的优化版本，成为工程、算法竞赛中最常用的最短路算法。

本文将从图的密度出发，分别讲解Dijkstra的稠密图暴力版、稀疏图堆优化版，并简单提及理论最优的斐波那契堆优化版，附上可直接运行的Python代码与详细解析。

算法核心原理

Dijkstra的核心逻辑只有两步，贯穿所有实现版本：

1. 贪心选择：每次从「未确定最短路径」的节点中，选出距离起点最近的节点（这是贪心策略的核心）；
2. 松弛操作：用这个刚选中的节点，更新它所有邻接节点的最短距离（节点u距离 = min(原距离, 选中节点距离 + 边权)）。

重复上述过程，直到所有节点的最短路径都被确定。

1. 稠密图实现：暴力枚举（O(n²)）

适用场景

节点数n较少，边数m ≈ n²（完全图、稠密连通图）；
使用邻接矩阵存储图，暴力查找最近节点，无额外数据结构开销。

完整代码

# 初始化：无穷大、节点数n、源点k（1-based索引）INF=float('inf')n=5# 示例：5个节点k=1# 示例：源点为第1个节点# 邻接矩阵：g[i][j] 表示节点i到j的边权，无连接则为INFg=[[0,2,INF,1,INF],[2,0,3,INF,INF],[INF,3,0,INF,2],[1,INF,INF,0,4],[INF,INF,2,4,0]]# 初始化距离数组：d[i] = 起点到i的最短距离d=[INF]*n# 前驱数组：pre[i] 记录i的最短路径上一个节点，用于回溯路径pre=[-1]*n# 已确定最短路径的节点集合visited=set()# 源点距离初始化为0（转换为0-based索引）start=k-1d[start]=0# 核心循环：n-1次即可确定所有节点的最短路for_inrange(n-1):# 步骤1：贪心选择 -> 找未访问的、距离起点最近的节点xx=-1foruinrange(n):ifunotinvisitedand(x==-1ord[u]<d[x]):x=u# 标记为已确定最短路径visited.add(x)# 步骤2：松弛操作 -> 用x更新所有节点的距离foruinrange(n):ifd[u]>d[x]+g[x][u]:d[u]=d[x]+g[x][u]pre[u]=x# 回溯最短路径：从终点v回到起点defget_path(v):path=[]current=v-1# 转换为0-based索引whilecurrent!=-1:path.append(current+1)# 转回1-based索引（符合日常习惯）current=pre[current]# 反转得到 起点->终点 的顺序returnpath[::-1]# 测试：输出起点到所有节点的距离+路径print("最短距离：",[d[i]foriinrange(n)])print("到节点5的路径：",get_path(5))

代码解析

1. 数据结构：邻接矩阵存储稠密图，visited集合记录已确定最短路径的节点；
2. 贪心选择：双重循环暴力查找最近节点，是时间复杂度O(n²)的来源；
3. 松弛操作：遍历所有节点更新距离，前驱数组pre用于还原路径；
4. 路径回溯：从终点反向遍历前驱数组，反转后得到正向最短路径。

2. 稀疏图实现：堆优化（O(mlogn)）

适用场景

节点数n大，边数m远小于n²（网络拓扑、地图、算法竞赛常规图）；
使用邻接表存储图，搭配二叉堆（小根堆）优化「贪心选择」，将查找最近节点的时间从O(n)降到O(logn)。

这是工程中最常用的Dijkstra实现。

完整代码

frommathimportinffromheapqimportheappop,heappush# 输入：n=节点数，m=边数，k=源点（0-based索引）n,m,k=map(int,input().split())# 邻接表：e[u] 存储 (v, 边权w)e=[[]for_inrange(n)]# 建图for_inrange(m):u,v,w=map(int,input().split())e[u].append((v,w))# 初始化距离数组d=[inf]*n d[k]=0# 小根堆：存储 (距离, 节点)，自动弹出最小距离hq=[(0,k)]# 核心循环whilehq:dx,x=heappop(hq)# 关键：跳过旧的、无效的距离（堆中可能存在冗余数据）ifdx>d[x]:continue# 松弛操作：遍历邻接节点forv,wine[x]:ifd[v]>d[x]+w:d[v]=d[x]+w heappush(hq,(d[v],v))# 输出源点到所有节点的最短距离print("源点到各节点的最短距离：",*d)

代码解析

1. 数据结构：邻接表存储稀疏图，空间复杂度O(m)，远优于邻接矩阵；
2. 堆优化：Python内置heapq实现小根堆，每次O(logn)取出最近节点；
3. 冗余跳过：堆中可能存在同一节点的多个距离记录，仅保留最小的有效距离；
4. 时间复杂度：O(mlogn)，是稀疏图的最优实用解法。

3. 斐波那契堆优化（理论最优）

核心特点

• 二叉堆的extract-min时间为O(logn)，而斐波那契堆将其优化为均摊O(1)，decrease-key也为均摊O(1)；
• 最终时间复杂度：O(m + nlogn)，是Dijkstra的理论最优复杂度；
• 致命缺点：实现极其复杂，常数开销极大，工程中几乎不使用，仅存在于算法理论中。

完整代码（仅作参考）

frommathimportinf# 斐波那契堆节点类classFibonacciHeapNode:def__init__(self,key,value):self.key=key self.value=value self.parent=Noneself.child=Noneself.left=self self.right=self self.degree=0self.mark=Falseself.in_heap=True# 斐波那契堆实现classFibonacciHeap:def__init__(self):self.min_node=Noneself.node_count=0self.root_list=Nonedefinsert(self,key,value):new_node=FibonacciHeapNode(key,value)ifself.root_listisNone:self.root_list=new_nodeelse:new_node.right=self.root_list new_node.left=self.root_list.left self.root_list.left.right=new_node self.root_list.left=new_nodeifself.min_nodeisNoneornew_node.key<self.min_node.key:self.min_node=new_node self.node_count+=1returnnew_nodedefextract_min(self):ifself.min_nodeisNone:returnNonez=self.min_node z.in_heap=Falseifz.childisnotNone:child=z.childwhileTrue:next_child=child.right child.parent=Noneself._add_to_root_list(child)ifnext_child==z.child:breakchild=next_child self._remove_from_root_list(z)ifz==z.right:self.root_list=Noneself.min_node=Noneelse:self.min_node=z.right self._consolidate()self.node_count-=1returnzdefdecrease_key(self,node,new_key):ifnotnode.in_heapornew_key>node.key:returnnode.key=new_key y=node.parentifyisnotNoneandnode.key<y.key:self._cut(node,y)self._cascading_cut(y)ifnode.key<self.min_node.key:self.min_node=nodedef_add_to_root_list(self,node):ifself.root_listisNone:self.root_list=node node.left=node.right=nodeelse:node.right=self.root_list node.left=self.root_list.left self.root_list.left.right=node self.root_list.left=nodedef_remove_from_root_list(self,node):left=node.left right=node.right left.right=right right.left=leftifself.root_list==node:self.root_list=rightdef_cut(self,node,parent):ifparent.child==node:parent.child=node.rightifnode!=node.rightelseNoneifparent.childisnotNone:node.left.right=node.right node.right.left=node.left parent.degree-=1self._add_to_root_list(node)node.parent=Nonenode.mark=Falsedef_cascading_cut(self,node):parent=node.parentifparentisnotNone:ifnotnode.mark:node.mark=Trueelse:self._cut(node,parent)self._cascading_cut(parent)def_consolidate(self):degree_table={}ifself.root_listisNone:returnroots=[]current=self.root_listwhileTrue:roots.append(current)current=current.rightifcurrent==self.root_list:breakfornodeinroots:d=node.degreewhiledindegree_table:other=degree_table[d]ifnode.key>other.key:node,other=other,node self._link(other,node)degree_table.pop(d)d+=1degree_table[d]=node self.min_node=Noneself.root_list=Nonefornodeindegree_table.values():self._add_to_root_list(node)ifself.min_nodeisNoneornode.key<self.min_node.key:self.min_node=nodedef_link(self,child,parent):self._remove_from_root_list(child)child.left=child.right=child child.parent=parentifparent.childisNone:parent.child=childelse:child.right=parent.child child.left=parent.child.left parent.child.left.right=child parent.child.left=child parent.degree+=1child.mark=Falsedefis_empty(self):returnself.node_count==0# Dijkstra主逻辑n,m,k=map(int,input().split())e=[[]for_inrange(n)]for_inrange(m):u,v,w=map(int,input().split())e[u].append((v,w))d=[inf]*n d[k]=0hq=FibonacciHeap()nodes_ref=[None]*n nodes_ref[k]=hq.insert(0,k)whilenothq.is_empty():min_node=hq.extract_min()ifnotmin_node:breakdx,x=min_node.key,min_node.valueifdx>d[x]:continueforv,wine[x]:ifd[v]>d[x]+w:d[v]=d[x]+wifnodes_ref[v]andnodes_ref[v].in_heap:hq.decrease_key(nodes_ref[v],d[v])else:nodes_ref[v]=hq.insert(d[v],v)print(*d)

总结

Dijkstra算法的三种实现，核心是根据图的密度选择方案：

1. 稠密图：暴力枚举O(n²)，代码极简，小图首选；
2. 稀疏图：二叉堆优化O(mlogn)，工程通用、算法竞赛标配；
3. 斐波那契堆：理论最优O(m+nlogn)，实现复杂，无实用价值。

⚠️ 重要提醒：Dijkstra算法仅适用于边权非负的图，如果图中存在负权边，请使用Bellman-Ford或SPFA算法。