2025 高中信息技术数据与计算之算法的最短路径算法课件

一、教学背景与目标定位：为何要学最短路径算法？演讲人教学背景与目标定位：为何要学最短路径算法？01实践应用与编程实现：从理论到代码的跨越02核心概念筑基：从“图”到“最短路径”的逻辑起点03总结与升华：最短路径算法的思维价值04目录2025高中信息技术数据与计算之算法的最短路径算法课件作为深耕高中信息技术教学十余年的一线教师，我始终认为，算法是数据与计算模块的核心纽带，而最短路径算法则是连接理论与实践的典型范例。今天，我们将围绕“最短路径算法”展开系统学习，从基础概念到经典算法，从理论推导到实践应用，逐步揭开这一算法的神秘面纱。01教学背景与目标定位：为何要学最短路径算法？1课程标准的要求《普通高中信息技术课程标准（2017年版2020年修订）》在“数据与计算”模块中明确指出：学生需“理解数据处理与算法设计在信息社会中的重要性”，并“掌握一种或多种算法的基本思想，能用恰当的方法表示算法”。最短路径算法作为图论中的经典问题，既是算法设计的典型案例，也是解决实际问题的重要工具，完全契合课标的能力培养要求。2现实需求的驱动在日常生活中，我们每天都在与“最短路径”打交道：导航软件推荐的“最快路线”、外卖平台规划的配送路径、物流系统优化的运输方案……这些场景的核心都是最短路径算法的应用。通过学习这一算法，学生不仅能理解技术背后的原理，更能培养“用计算思维解决实际问题”的核心素养。3教学目标的分层设计基于上述背景，本课件的教学目标可分为三个维度：知识目标：理解图的基本概念（顶点、边、权值），掌握Dijkstra算法与Floyd-Warshall算法的核心思想与执行步骤；能力目标：能运用两种算法解决单源最短路径与多源最短路径问题，能通过伪代码或简单程序实现算法逻辑；素养目标：体会算法设计中“贪心策略”“动态规划”等思想的普适性，培养从实际问题中抽象数学模型的能力。02核心概念筑基：从“图”到“最短路径”的逻辑起点1图：最短路径问题的数学模型要理解最短路径算法，首先需要明确其“舞台”——图（Graph）。图是由顶点（Vertex，也叫节点）和边（Edge）组成的数学结构，通常记为(G=(V,E))，其中(V)是顶点的集合，(E)是边的集合。顶点：表示实际问题中的“实体”，例如地图中的城市、社交网络中的用户；边：表示实体间的“关系”，例如城市间的道路、用户间的关注；权值（Weight）：边的附加属性，表示关系的“强度”或“代价”，例如道路的长度、通行时间，或社交关系的亲密度。举个具体例子：假设我们有一个“校园地图”（图1），顶点是教学楼、食堂、图书馆等地点，边是连接它们的道路，权值是道路的步行时间（分钟）。此时，“从教学楼到图书馆的最短路径”就转化为：在图中找到一条从起点到终点的路径，使得路径上所有边的权值之和最小。2最短路径的定义与分类明确了图的模型后，我们需要定义“最短路径”。严格来说，最短路径是指在图中，从起点(s)到终点(t)的所有可能路径中，权值之和最小的那条路径。根据问题的输入范围，最短路径问题可分为两类：01多源最短路径（All-PairsShortestPaths）：求图中每对顶点((u,v))之间的最短路径（如物流系统中“任意两个仓库间的最优运输路线”）。03单源最短路径（Single-SourceShortestPaths）：给定一个起点(s)，求(s)到图中所有其他顶点的最短路径（如导航软件中“从当前位置到所有目的地的最短路线”）；022最短路径的定义与分类这两类问题对应不同的经典算法：单源问题常用Dijkstra算法（适用于非负权图）或Bellman-Ford算法（可处理负权图）；多源问题则常用Floyd-Warshall算法（适用于小规模图）。考虑到高中阶段的知识难度，本课件重点讲解Dijkstra算法与Floyd-Warshall算法。三、经典算法解析：从Dijkstra到Floyd-Warshall的思维演进1Dijkstra算法：贪心策略下的单源最短路径求解1.1算法核心思想Dijkstra算法由荷兰计算机科学家艾兹格迪科斯彻（EdsgerDijkstra）于1956年提出，其核心是贪心策略：每次选择当前已知最短路径的顶点，更新其邻接顶点的最短距离，逐步扩展“已确定最短路径的顶点集合”，直至覆盖所有顶点。1Dijkstra算法：贪心策略下的单源最短路径求解1.2算法步骤详解（以非负权无向图为例）为了更直观地理解，我们以“校园地图”（图1）为例，假设起点是教学楼（顶点A），其他顶点为食堂（B）、图书馆（C）、操场（D）、校门（E），边权为步行时间（分钟），具体结构如下：(A-B:5)，(A-D:8)，(B-C:3)，(B-E:9)，(C-D:2)，(C-E:4)，(D-E:7)1Dijkstra算法：贪心策略下的单源最短路径求解初始化定义距离数组(dist[])，其中(dist[v])表示起点到顶点(v)的当前最短距离。初始时，(dist[A]=0)（起点到自身距离为0），其他顶点(dist[v]=\infty)（无穷大，表示初始不可达）；定义集合(S)，记录已确定最短路径的顶点，初始时(S=\emptyset)；定义优先队列（或最小堆）用于选择当前距离最小的顶点，初始时队列中只有(A)（距离0）。1Dijkstra算法：贪心策略下的单源最短路径求解初始化步骤2：迭代更新从队列中取出距离最小的顶点(u)（首次为(A)），将其加入集合(S)；遍历(u)的所有邻接顶点(v)，计算新的距离(temp=dist[u]+weight(u,v))；如果(temp<dist[v])，则更新(dist[v]=temp)，并将(v)加入队列（或更新队列中(v)的距离）；重复上述步骤，直到队列为空（所有顶点都加入(S)）。1Dijkstra算法：贪心策略下的单源最短路径求解初始化步骤3：结果输出最终(dist[])数组即为起点到所有顶点的最短距离。以“校园地图”为例，执行Dijkstra算法后，(dist[E])的值应为(A→B→C→E)，总时间(5+3+4=12)分钟（而非直接(A→D→E)的(8+7=15)分钟，或(A→B→E)的(5+9=14)分钟）。1Dijkstra算法：贪心策略下的单源最短路径求解1.3算法特点与适用场景优势：时间复杂度为(O((V+E)\logV))（使用优先队列优化），效率较高；01限制：仅适用于边权非负的图（若存在负权边，贪心策略可能失效，例如某条路径绕负权边后总距离更小，但Dijkstra会错误地认为已找到最短路径）；02应用场景：导航软件的实时路径规划（道路通行时间通常非负）、网络路由协议（如OSPF协议中的最短路径计算）。033.2Floyd-Warshall算法：动态规划下的多源最短路径求解041Dijkstra算法：贪心策略下的单源最短路径求解2.1算法核心思想Floyd-Warshall算法由罗伯特弗洛伊德（RobertFloyd）和斯蒂芬沃舍尔（StephenWarshall）共同提出，其核心是动态规划：通过逐步引入中间顶点，更新每对顶点间的最短路径。具体来说，设(d[k][i][j])表示从(i)到(j)，且中间顶点编号不超过(k)的最短路径长度。状态转移方程为：[d[k][i][j]=\min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j])]最终(d[n-1][i][j])（(n)为顶点数）即为(i)到(j)的最短路径长度。1Dijkstra算法：贪心策略下的单源最短路径求解2.2算法步骤详解（以有向图为例）为简化计算，Floyd-Warshall算法通常使用二维数组(dist[][])直接存储每对顶点的最短距离，初始时(dist[i][j])为边(i→j)的权值（无边则为(\infty)），(dist[i][i]=0)。1Dijkstra算法：贪心策略下的单源最短路径求解初始化距离矩阵假设我们有一个包含4个顶点（A、B、C、D）的有向图，边权如下：(A→B:2)，(A→C:5)，(B→C:1)，(B→D:3)，(C→D:1)，其他边权为(\infty)。初始距离矩阵(dist)为：[\begin{bmatrix}0&2&5&\infty\\infty&0&1&3\\infty&\infty&0&1\\infty&\infty&\infty&0\1Dijkstra算法：贪心策略下的单源最短路径求解初始化距离矩阵\end{bmatrix}]步骤2：逐步引入中间顶点k=0（顶点A）：检查所有(i→j)的路径是否经过A。例如，(B→A)无边（(dist[B][A]=\infty)），因此无更新；k=1（顶点B）：检查路径是否经过B。例如，(A→C)的当前距离是5，但(A→B→C)的距离是(2+1=3)，更小，因此更新(dist[A][C]=3)；k=2（顶点C）：检查路径是否经过C。例如，(A→D)的当前距离是(\infty)，但(A→C→D)的距离是(3+1=4)（因(A→C)已更新为3），因此更新(dist[A][D]=4)；1Dijkstra算法：贪心策略下的单源最短路径求解初始化距离矩阵k=3（顶点D）：无进一步更新，算法结束。最终距离矩阵中，(dist[A][D]=4)，即(A→B→C→D)为最短路径。1Dijkstra算法：贪心策略下的单源最短路径求解2.3算法特点与适用场景01优势：代码简洁（三重循环即可实现），可处理负权边（但不能处理负权环，否则最短路径无意义）；02限制：时间复杂度为(O(V^3))，适用于顶点数较少的图（如(V\leq200)）；03应用场景：社交网络中的“共同好友最短路径”（顶点数有限）、电路设计中的信号传输延迟计算（需考虑多起点多终点）。3算法对比与选择策略为帮助学生灵活选择算法，我们需总结两者的差异（表1）：|维度|Dijkstra算法|Floyd-Warshall算法||--------------|-------------------------------|-----------------------------||问题类型|单源最短路径|多源最短路径||权值要求|非负权|允许负权（无负权环）||时间复杂度|(O((V+E)\logV))（优化后）|(O(V^3))||空间复杂度|(O(V+E))|(O(V^2))||适用场景|大规模图、非负权|小规模图、需多源结果|03实践应用与编程实现：从理论到代码的跨越1实际问题的建模与分析以“外卖配送路径优化”为例：某外卖员需从配送站（顶点S）出发，依次为3个客户（顶点A、B、C）送餐，要求总行程最短。此时，问题可拆解为两步：单源最短路径：计算S到A、S到B、S到C的最短距离；多源最短路径：计算A到B、A到C、B到C的最短距离，用于规划客户间的最优顺序（如S→A→B→CvsS→B→A→C）。通过Dijkstra算法求解第一步，Floyd-Warshall算法求解第二步，即可得到最优配送路线。importheapqdefdijkstra(graph,start):1dist={node:float('inf')fornodeingraph}2dist[start]=03heap=[(0,start)]4visited=set()5whileheap:6current_dist,u=heapq.heappop(heap)7ifuinvisited:8continue9importheapqvisited.add(u)ifdist[v]current_dist+weight:dist[v]=current_dist+weightheapq.heappush(heap,(dist[v],v))returndist示例图（校园地图）graph={'A':{'B':5,'D':8},'B':{'A':5,'C':3,'E':9},forv,weightingraph[u].items():importheapq'C':{'B':3,'D':2,'E':4},'D':{'A':8,'C':2,'E':7},'E':{'B':9,'C':4,'D':7}}print(dijkstra(graph,'A'))#输出：{'A':0,'B':5,'C':8,'D':8,'E':12}4.2.2Floyd-Warshall算法的Python实现deffloyd_warshall(graph):importheapqn=len(graph)forkinrange(n):foriinrange(n):forjinrange(n):ifdist[i][j]dist[i][k]+dist[k][j]:dist[i][j]=dist[i][k]+dist[k][j]returndist示例图（4顶点有向图）初始距离矩阵（∞用1e9表示）dist=[row[:]forrowingraph]importheapqgraph=[[0,2,5,1e9],[1e9,0,1,3],[1e9,1e9,0,1],[1e9,1e9,1e9,0]]result=floyd_warshall(graph)forrowinresult:print([xifx!=1e9else'∞'forxinrow])importheapq输出：[0,2,3,4][∞,0,1,2][∞,∞,∞,0][∞,∞,0,1]3学生实践建议为强化理解，可设计分层实践任务：基础任务：手动模拟Dijkstra算法在“校园地图”中的执行过程，验证(dist[