2025 高中信息技术数据结构图的最短路径 Dijkstra 算法详解课件

引言：从生活场景到算法需求的自然过渡演讲人CONTENTS引言：从生活场景到算法需求的自然过渡知识铺垫：图与最短路径的基础认知算法拆解：Dijkstra的核心逻辑与步骤详解实践深化：算法的实现与常见误区总结：算法思想的升华与学科价值的重申目录01引言：从生活场景到算法需求的自然过渡引言：从生活场景到算法需求的自然过渡作为一名深耕高中信息技术教学十余年的教师，我常观察到学生对“算法”的认知往往始于具体问题。比如，当他们用导航软件查询“从学校到市中心的最快路线”时，手机屏幕上那条用绿色高亮标出的路径，背后就藏着经典的最短路径算法——Dijkstra算法。这让我意识到，将抽象的算法与真实生活场景结合，是帮助高中生理解图与算法的关键。在2023版《普通高中信息技术课程标准》中，“数据结构与算法”模块明确要求学生“理解图的基本概念，掌握求解最短路径的常用算法”。而Dijkstra算法作为求解单源最短路径的经典方法，既是课程重点，也是培养学生计算思维的重要载体。接下来，我们将从图的基础概念出发，逐步拆解Dijkstra算法的核心逻辑，最终通过实践应用深化理解。02知识铺垫：图与最短路径的基础认知1图的基本概念回顾要理解Dijkstra算法，首先需要明确“图”的结构。在信息技术领域，图（Graph）是由顶点（Vertex，也称为节点）和边（Edge）组成的非线性数据结构。根据边是否带权值，图可分为无权图和带权图；根据边的方向性，又可分为无向图和有向图。以城市交通网络为例：顶点：各个交通节点（如学校、商场、地铁站）；边：连接节点的道路；权值：道路的长度、通行时间或拥堵程度（带权图的典型特征）。在带权图中，边的权值通常表示顶点间的“代价”。我们的目标，是找到从起点（源点）到终点的路径中，权值之和最小的那条——这就是“最短路径问题”。2最短路径问题的分类与Dijkstra算法的适用场景最短路径问题主要分为两类：单源最短路径：求从一个源点到所有其他顶点的最短路径（如“从学校出发到各个商场的最短路线”）；多源最短路径：求所有顶点对之间的最短路径（如“任意两个商场之间的最短路线”）。Dijkstra算法由荷兰计算机科学家艾兹格迪科斯彻（EdsgerW.Dijkstra）于1956年提出，专门解决带权有向图或无向图的单源最短路径问题，但要求图中所有边的权值非负（若存在负权边，需改用Bellman-Ford算法）。这一限制在现实场景中具有合理性——道路长度、时间等“代价”通常不会为负数。03算法拆解：Dijkstra的核心逻辑与步骤详解1算法的核心思想：贪心策略与松弛操作Dijkstra算法的核心是“贪心选择”（GreedyChoice）：每次选择当前已知最短路径的顶点，更新其邻接顶点的最短路径估计值。这一过程通过“松弛操作”（Relaxation）实现，即比较通过当前顶点到达邻接顶点的路径权值与已知的最短路径权值，若更优则更新。举个生活化的例子：假设你要从学校（源点S）去图书馆（顶点T），中途可能经过超市（顶点A）和公园（顶点B）。已知S到A的距离是3公里，A到T的距离是2公里（总5公里）；S到B的距离是4公里，B到T的距离是1公里（总5公里）。此时若发现A到B的距离是1公里（S→A→B→T总距离3+1+1=5公里），虽然总距离未变，但可能通过A更新B的最短路径估计值（原S→B是4公里，现在S→A→B是3+1=4公里，相等则不更新）。2算法的具体步骤（以带权无向图为例）为便于理解，我们以一个具体的图结构为例（见图1）：顶点集合V={S,A,B,C,D}，边集合E={(S,A,2),(S,B,5),(A,B,1),(A,C,3),(B,C,1),(B,D,4),(C,D,2)}，权值表示两点间距离。目标是求源点S到所有其他顶点的最短路径。2算法的具体步骤（以带权无向图为例）初始化数据结构距离数组dist[]：记录源点S到各顶点的当前最短距离估计值。初始时，dist[S]=0（源点到自身距离为0），其他顶点设为无穷大（∞）。标记数组visited[]：记录顶点是否已确定最短路径（初始全为false）。前驱数组prev[]：记录各顶点的前驱顶点（用于最后回溯路径，初始为null）。初始状态：dist=[0,∞,∞,∞,∞]（对应S,A,B,C,D）visited=[false,false,false,false,false]prev=[null,null,null,null,null]2算法的具体步骤（以带权无向图为例）初始化数据结构步骤2：迭代选择当前最短路径顶点每次从未访问的顶点中选择dist最小的顶点u，标记为已访问（visited[u]=true），然后对u的所有邻接顶点v进行松弛操作。第1轮迭代：未访问顶点中dist最小的是S（dist=0）。标记S为已访问。S的邻接顶点是A（边权2）和B（边权5）。对于A：当前dist[A]=∞，通过S到达A的距离是0+2=2<∞，更新dist[A]=2，prev[A]=S。对于B：当前dist[B]=∞，通过S到达B的距离是0+5=5<∞，更新dist[B]=5，prev[B]=S。2算法的具体步骤（以带权无向图为例）初始化数据结构更新后：dist=[0,2,5,∞,∞]visited=[true,false,false,false,false]第2轮迭代：未访问顶点为A,B,C,D，其中dist最小的是A（dist=2）。标记A为已访问。A的邻接顶点是S（已访问）、B（边权1）、C（边权3）。对于B：当前dist[B]=5，通过A到达B的距离是2+1=3<5，更新dist[B]=3，prev[B]=A。2算法的具体步骤（以带权无向图为例）初始化数据结构对于C：当前dist[C]=∞，通过A到达C的距离是2+3=5<∞，更新dist[C]=5，prev[C]=A。更新后：dist=[0,2,3,5,∞]visited=[true,true,false,false,false]第3轮迭代：未访问顶点为B,C,D，其中dist最小的是B（dist=3）。标记B为已访问。B的邻接顶点是S（已访问）、A（已访问）、C（边权1）、D（边权4）。2算法的具体步骤（以带权无向图为例）初始化数据结构对于C：当前dist[C]=5，通过B到达C的距离是3+1=4<5，更新dist[C]=4，prev[C]=B。对于D：当前dist[D]=∞，通过B到达D的距离是3+4=7<∞，更新dist[D]=7，prev[D]=B。更新后：dist=[0,2,3,4,7]visited=[true,true,true,false,false]2算法的具体步骤（以带权无向图为例）初始化数据结构第4轮迭代：未访问顶点为C,D，其中dist最小的是C（dist=4）。标记C为已访问。C的邻接顶点是A（已访问）、B（已访问）、D（边权2）。对于D：当前dist[D]=7，通过C到达D的距离是4+2=6<7，更新dist[D]=6，prev[D]=C。更新后：dist=[0,2,3,4,6]visited=[true,true,true,true,false]第5轮迭代：未访问顶点只剩D（dist=6），标记为已访问。无邻接顶点未处理，算法结束。3结果分析与路径回溯最终dist数组为[0,2,3,4,6]，表示：S到A的最短距离是2（路径S→A）；S到B的最短距离是3（路径S→A→B）；S到C的最短距离是4（路径S→A→B→C）；S到D的最短距离是6（路径S→A→B→C→D）。通过prev数组回溯路径时，从目标顶点反向查找前驱，直到回到源点S。例如D的前驱是C，C的前驱是B，B的前驱是A，A的前驱是S，因此完整路径为S→A→B→C→D。04实践深化：算法的实现与常见误区1算法的伪代码实现（以邻接表存储图为例）functionDijkstra(图G,源点S):初始化visited数组，全为false初始化优先队列（最小堆），将(S,0)加入队列while队列不为空:取出队列中距离最小的顶点u及当前距离difvisited[u]为true:跳过（已处理过更短的路径）visited[u]=truefor每个邻接顶点v及边权winG[u]:ifdist[v]d+w:初始化dist数组，dist[S]=0，其他为∞1算法的伪代码实现（以邻接表存储图为例）dist[v]=d+wprev[v]=u将(v,dist[v])加入队列returndist,prev关键说明：优先队列（最小堆）用于高效选择当前距离最小的顶点，时间复杂度从O(n²)优化为O(mlogn)（n为顶点数，m为边数）；若图用邻接矩阵存储，选择最小距离顶点的操作为O(n)，总时间复杂度为O(n²)，适合顶点数较少的图。2学生常见误区与教学对策在多年教学中，我发现学生容易在以下环节出错：松弛操作的方向混淆：误以为“松弛”是更新当前顶点的距离，实际上是通过当前顶点更新其邻接顶点的距离。对策：用箭头标注“u→v”的方向，强调“从u出发影响v”。优先队列的作用理解不深：认为“每次必须按顶点顺序处理”，忽略了优先队列的“贪心选择”本质。对策：用不同颜色标记已访问顶点，对比顺序处理与优先队列处理的效率差异。负权边的干扰：直接应用Dijkstra算法到含负权边的图中，导致错误结果。对策：设计对比实验，用含负权边的图（如S→A权2，A→B权-3，S→B权5）演示Dijkstra的错误（会认为S→B最短是5，实际S→A→B是-1），引出负权边需用Bellman-Ford算法。3拓展应用：从理论到生活的迁移Dijkstra算法的应用远不止导航软件，还包括：网络路由：路由器通过Dijkstra算法（OSPF协议）计算到目标IP的最短路径；物流调度：快递分拨中心规划货车运输路线，最小化运输时间；游戏开发：NPC寻路时避开障碍物，选择最短移动路径。在课堂实践中，我常让学生用Excel表格模拟Dijkstra算法的执行过程（如表1），或用Python编写简化版代码（使用列表模拟优先队列），通过动手操作加深理解。05总结：算法思想的升华与学科价值的重申总结：算法思想的升华与学科价值的重申回顾本次课程，我们从生活中的路径规划问题出发，逐步拆解了Dijkstra算法的核心逻辑：通过贪心策略选择当前最短路径顶点，利用松弛操作更新邻接顶点的距离估计值，最终得到源点到所有顶点的最短路径。这一过程不仅是算法知识的学习，更是计算思维的培养——将复杂问题分解为可操作的步骤，通过局部最优逼近全局最优。作为高中信息技术教师，我始终认为：算法教学的本质不是记忆步骤，而是理解“为什么这样做”和“如何解决新问题”。Di