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

一、教学目标与知识铺垫：为何要学最短路径算法？演讲人01教学目标与知识铺垫：为何要学最短路径算法？02最短路径问题的定义与分类：从生活场景到数学模型03单源最短路径：Dijkstra算法的核心思想与实现04无权图的最短路径：BFS的特殊应用05算法对比与实际应用：如何选择合适的算法？06课堂实践与思维拓展：从理论到代码的跨越07总结与升华：最短路径算法的“道”与“术”目录2025高中信息技术数据结构的图的最短路径算法课件作为深耕中学信息技术教学十余年的教师，我始终认为，数据结构是计算机科学的基石，而图结构作为其中最复杂的非线性结构，其相关算法更是培养学生逻辑思维与问题解决能力的重要载体。今天，我们将聚焦“图的最短路径算法”，从基础概念到经典算法，逐步拆解、深入探究，帮助同学们构建完整的知识体系。01教学目标与知识铺垫：为何要学最短路径算法？1教学目标定位本节课的核心目标可分为三个层次：知识目标：理解图的基本概念（顶点、边、权值），掌握最短路径问题的定义；熟练应用Dijkstra算法、Floyd-Warshall算法解决单源/多源最短路径问题；明确不同算法的适用场景与局限性。能力目标：能通过手动模拟或简单编程实现算法流程；能根据实际问题特征（如是否含负权边、是否需要多源结果）选择合适算法；提升抽象建模与逻辑推理能力。素养目标：感受算法设计中“贪心策略”“动态规划”等思想的普适性；体会图结构在导航系统、网络路由、物流规划等真实场景中的应用价值，激发用计算思维解决实际问题的兴趣。2前置知识回顾在正式学习算法前，我们需要先明确图的基本概念与存储方式——这是理解最短路径问题的“地基”。图的定义：图（Graph）由顶点（Vertex）集合V和边（Edge）集合E组成，记为G=(V,E)。边可附带权值（Weight），表示顶点间的“距离”“成本”或“时间”。若边是有方向的（如A→B与B→A不同），则为有向图；否则为无向图。存储方式：邻接矩阵：用二维数组matrix[i][j]表示顶点i到j的边权（无边则为∞），空间复杂度O(n²)，适合稠密图（边数接近n²）。邻接表：用链表或数组存储每个顶点的邻接顶点及边权，空间复杂度O(n+e)（e为边数），适合稀疏图（边数远小于n²）。2前置知识回顾例如，某城市交通图可抽象为无向图：顶点是车站，边是道路，边权是车程时间；而互联网路由图则是有向图，边权可能表示网络延迟。明确这些概念后，我们正式进入最短路径问题的核心。02最短路径问题的定义与分类：从生活场景到数学模型1问题的直观描述A最短路径问题，本质是在图中找到从起点到终点的一条路径，使得路径上所有边的权值之和最小。它广泛存在于生活中：B导航软件（如高德地图）需要计算“从A到B的最快路线”；C物流调度系统需规划“仓库到各网点的最低成本运输路径”；D社交网络分析中，“两个人之间的最短关系链”也可视为无权图的最短路径问题（边权为1）。2问题的数学定义给定图G=(V,E)，权值函数w:E→R（R为实数集），对于顶点u,v∈V，最短路径P是u到v的路径中，满足Σw(e)最小的路径（e∈P）。若不存在路径，则记为∞。3问题的分类根据求解范围，最短路径问题可分为两类：单源最短路径（Single-SourceShortestPaths）：给定一个起点s，求s到所有其他顶点的最短路径（如导航中“从当前位置到所有目的地的路线”）。多源最短路径（All-PairsShortestPaths）：求图中每对顶点(u,v)之间的最短路径（如物流系统中“所有仓库到所有网点的最优路线”）。接下来，我们将针对这两类问题，分别学习经典算法。03单源最短路径：Dijkstra算法的核心思想与实现1Dijkstra算法的适用场景Dijkstra算法由荷兰计算机科学家EdsgerW.Dijkstra于1956年提出，适用于带权有向/无向图，且所有边权非负（权值≥0）。这是因为算法的贪心策略依赖“非负权值”保证：一旦某个顶点的最短距离被确定，后续不会出现更短的路径（若存在负权边，可能通过“绕路”得到更短路径，导致贪心策略失效）。2算法的核心思想：贪心策略Dijkstra算法的本质是“逐步扩展最短路径集合”。其核心步骤可概括为：初始化：设置起点s的距离为0，其他顶点距离为∞；维护一个“已确定最短路径”的集合S（初始为空）。选择当前最短距离顶点：从不在S中的顶点中，选择距离最小的顶点u，将其加入S（因边权非负，u的最短距离已确定）。松弛操作（Relaxation）：遍历u的所有邻接顶点v，若通过u到达v的路径更短（即distance[u]+w(u,v)distance[v]），则更新v的距离。重复：直到所有顶点都加入S，算法结束。3手动模拟：以具体案例理解流程为了直观感受算法，我们以图1为例（无向图，顶点A为起点）：顶点：A,B,C,D,E边权：A-B(2),A-C(5),B-C(1),B-D(3),C-E(4),D-E(1)步骤1：初始化distance[A]=0，其他为∞；S=∅。步骤2：选择距离最小的A（0），加入S。遍历A的邻接顶点B（2）、C（5），更新distance[B]=2，distance[C]=5。步骤3：S外最小距离是B（2），加入S。遍历B的邻接顶点A（已处理）、C（当前distance[C]=5，通过B的路径是2+1=3<5，更新为3）、D（2+3=5，更新distance[D]=5）。3手动模拟：以具体案例理解流程步骤4：S外最小距离是C（3），加入S。遍历C的邻接顶点A（已处理）、B（已处理）、E（3+4=7，更新distance[E]=7）。步骤5：S外最小距离是D（5），加入S。遍历D的邻接顶点B（已处理）、E（5+1=6<7，更新distance[E]=6）。步骤6：S外仅剩E（6），加入S，算法结束。最终各顶点最短距离：A(0),B(2),C(3),D(5),E(6)。4算法的时间复杂度与优化未优化版本：使用数组存储距离，每次选择最小距离顶点需遍历所有顶点，时间复杂度为O(n²)（n为顶点数）。堆优化版本：使用优先队列（最小堆）存储待处理顶点，每次取出最小距离顶点的时间为O(logn)，松弛操作总次数为O(e)（e为边数），时间复杂度优化为O(elogn)。这更适用于稀疏图（如n=1000，e=10000时，O(elogn)远小于O(n²)）。5注意事项：负权边的“陷阱”若图中存在负权边（如边权为-1），Dijkstra算法可能得到错误结果。例如，图2中A到B的直接边权为3，A到C边权为5，C到B边权为-3。正确的A到B最短路径是A→C→B（5-3=2），但Dijkstra算法会先处理B（距离3），认为其最短路径已确定，忽略后续更短的路径。因此，处理含负权边的单源最短路径问题需使用Bellman-Ford算法（高中阶段可选学）。四、多源最短路径：Floyd-Warshall算法的动态规划思想1问题需求与算法选择当需要计算图中每对顶点(u,v)的最短路径时，若使用Dijkstra算法需运行n次（n为顶点数），时间复杂度为O(n³)（堆优化后为O(nelogn)）。而Floyd-Warshall算法（简称Floyd算法）通过动态规划思想，仅需O(n³)时间即可解决，且允许边权为负（但不能存在负权环——环的总权值为负，会导致路径无限缩短）。2动态规划的核心：中间顶点的逐步引入Floyd算法的关键在于“允许路径经过中间顶点k，并逐步扩展k的范围”。定义状态dist[k][i][j]为从i到j，且中间顶点编号不超过k的最短路径长度。状态转移方程为：01其含义是：i到j的最短路径，要么不经过k（即dist[k-1][i][j]），要么经过k（即i→k→j的路径和）。通过逐步将k从1到n（顶点编号）遍历，最终dist[n][i][j]即为i到j的最短路径。03dist[k][i][j]=min(dist[k-1][i][j],dist[k-1][i][k]+dist[k-1][k][j])023空间优化与实现步骤由于计算dist[k]时仅需dist[k-1]的数据，因此可将空间复杂度从O(n³)优化为O(n²)（使用二维数组直接更新）。具体步骤如下：初始化距离矩阵：dist[i][j]初始为i到j的直接边权（无边则为∞），dist[i][i]=0（顶点到自身距离为0）。三层循环更新：对每个k（1≤k≤n），对每对i,j（1≤i,j≤n），检查是否通过k可缩短i到j的距离，即dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])。4手动模拟：小图验证算法逻辑以图3为例（有向图，顶点A,B,C）：1初始化矩阵：2dist=[3[0,2,8],//A到A,B,C4[∞,0,3],//B到A,B,C5[-4,∞,0]//C到A,B,C6]7k=A（顶点A作为中间点）：8检查所有i,j：9边权：A→B(2),B→C(3),A→C(8),C→A(-4)104手动模拟：小图验证算法逻辑k=C（顶点C作为中间点）：B→A：当前是∞，通过B→A（无直接边）或B→A（中间点A无意义），无更新。C→B：当前是∞，C→A→B的距离是-4+2=-2<∞，更新dist[C][B]=-2。k=B（顶点B作为中间点）：A→C：当前是8，A→B→C的距离是2+3=5<8，更新dist[A][C]=5。C→B→C：C→B=-2，B→C=3，总距离1，但dist[C][C]已是0，无需更新。0304050601024手动模拟：小图验证算法逻辑A→C→A：A→C=5，C→A=-4，总距离1<dist[A][A]=0？不，因为顶点到自身距离固定为0。B→C→A：B→C=3，C→A=-4，总距离-1<dist[B][A]=∞，更新dist[B][A]=-1。最终矩阵：dist=[[0,2,5],//A到各点[-1,0,3],//B到各点[-4,-2,0]//C到各点]5负权环的检测若图中存在负权环（如i→k→j→i的总权值<0），则Floyd算法会在更新过程中发现dist[i][i]0（顶点到自身的距离被更新为负数），此时可判定存在负权环，最短路径问题无解（因可无限绕环缩短路径）。04无权图的最短路径：BFS的特殊应用1无权图的特性与算法选择无权图可视为边权均为1的带权图。此时，最短路径等价于“最少边数的路径”。对于这类问题，广度优先搜索（BFS）比Dijkstra算法更高效，因为BFS按层遍历顶点，首次访问某顶点时的路径即为最短路径（时间复杂度O(n+e)）。2BFS实现最短路径的步骤以无向无权图（顶点A为起点）为例：初始化队列：将起点A入队，标记距离为0。层序遍历：每次取出队首顶点u，遍历其所有邻接顶点v。若v未被访问过，设置v的距离为u的距离+1，标记已访问，将v入队。终止条件：队列为空时，所有可达顶点的最短距离已确定。3对比与总结BFS与Dijkstra算法在无权图中的关系：Dijkstra算法在无权图中（边权=1）等价于BFS，因为优先队列每次取出的是距离最小（即层数最小）的顶点。但BFS无需维护优先队列，实现更简单，效率更高。05算法对比与实际应用：如何选择合适的算法？1算法特性对比表|算法|问题类型|边权要求|时间复杂度|适用场景||----------------|----------------|----------------|-------------|---------------------------||Dijkstra（未优化）|单源|非负|O(n²)|稠密图（如城市全连接路网）||Dijkstra（堆优化）|单源|非负|O(elogn)|稀疏图（如社交网络）||Floyd-Warshall|多源|无负权环|O(n³)|小规模多源问题（n≤100）|1算法特性对比表|BFS|单源（无权图）|边权=1|O(n+e)|无权图最短边数问题|2实际问题中的选择策略1若问题是“从家到公司的最快路线”（单源，道路时间≥0），选Dijkstra算法（堆优化）。2若问题是“所有城市对之间的最短航线”（多源，可能含负权折扣），选Floyd算法（需确保无负权环）。3若问题是“社交平台中两人的最少共同好友数”（无权图），选BFS。06课堂实践与思维拓展：从理论到代码的跨越1手动模拟练习（5分钟）给定有向图（顶点A,B,C,D，边权：A→B(1),A→C(4),B→C(2),B→D(5),C→D(1)），以A为起点，用Dijkstra算法计算各顶点最短距离。（参考答案：B=1,C=3（A→B→C）,D=4（A→B→C→D））2编程实现建议（课后任务）对于有编程基础的同学，可尝试用Python实现Dijkstra算法（堆优化版本），步骤如下：使用优先队列（heapq模块