《计算机算法通俗教程》课件 王丰 第8-12章 分治 -图论算法

8分治8.1分治算法概述8.2二分答案8.3典型分治例题8.1分治算法概述分治算法是一种非常重要的算法设计思想。它的核心策略是将一个复杂的大问题分解为若干个规模较小、相互独立且与原问题形式相同的子问题，递归地解决这些子问题，然后将各子问题的解合并，从而得到原问题的解。这种策略在处理大规模数据或复杂计算时非常有效，能够显著降低时间复杂度。本章我们将深入探讨分治算法的基本原理、适用条件，并通过经典案例掌握其应用。定义：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。核心思想：分：分解问题，将大问题分解为多个规模较小的子问题。治：合并结果，将子问题的解合并得到原问题的解。实现方式：通常采用递归的方式实现。递归能很好地匹配分治的“分解”与“回溯”过程。适用问题特征：问题规模缩小到一定程度就容易解决。问题可以分解为若干个规模较小的相同问题。子问题的解可以合并为原问题的解。子问题相互独立（无公共子问题）。经典应用：二分搜索、归并排序、快速排序大整数乘法、棋盘覆盖最接近点对问题、循环比赛日程表二分答案是分治算法的经典应用，通过不断猜测中间值并验证，在已知答案范围且具有单调性的场景中快速求解。定义以二分搜索的方式查找答案，是分治算法的一种简单应用。基本定义适用场景1.无法直接求解，但知道答案区间。2.答案在区间内具有单调性。适用场景核心思想通过不断猜测答案并验证其正确性，快速缩小搜索范围，最终找到符合条件的解。核心思想8.2.1二分答案概述问题描述：从n条绳子中切割出m条长度相同的绳段，求绳段的最大长度。解题思路：1.确定答案范围：[最长绳长/m,总绳长/m]。2.二分搜索：猜测一个长度mid，检查能否切割出m段。3.根据检查结果调整搜索范围，直到找到最大值。1boolCheck(intlen){...}//检查能否切割出m段2voidSearch(intL,intR){...}//二分搜索最大长度8.2.2切割绳子已知条件：贷款总额、每月还款额、还款总月数。求解目标：计算贷款的月利率。问题描述1.确定范围：利率范围[0,300]。2.二分搜索：猜测利率mid，检查m个月能否还清。3.注意事项：实数二分，循环条件while(l<r-0.05)。解题思路doublel=0,r=300;while(l<r-0.05){doublemid=(l+r)/2;if(check(mid))

{

ans=mid;

l

=mid;

}else

r

=mid;}核心代码逻辑8.2.3银行贷款问题问题描述：找出序列中连续且非空的一段，使其和最大。分治策略：1.分解：将数组分成左右两半。2.求解：递归求解左右两半的最大子段和。3.合并：求解跨越中点的最大子段和，最终结果为三者中的最大值。跨越中点的处理：以中点为基准，分别向左右两侧搜索最大子段，再合并。8.3.1最大子段和最大子段和核心代码：递归实现分治策略intsubsegment(intleft,intright){if(left==right)returna[left];intmid=(left+right)/2;intleftmax=subsegment(left,mid);intrightmax=subsegment(mid+1,right);//计算跨越中点的最大子段和intsum1=MinInt,sum2=MinInt;for(inti=mid,sum=0;i>=left;i--){...}//向左搜索最大子段和for(inti=mid+1,sum=0;i<=right;i++){...}//向右搜索最大子段和returnmax(max(leftmax,rightmax),sum1+sum2);}问题描述：给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多只允许完成一笔交易（即买入和卖出一支股票）。分治策略：1.分解：将价格序列分成左右两半。2.求解：递归求解左右两半的最大利润。3.合并：求解左半部分买入、右半部分卖出的最大利润，最终结果为三者中的最大值。算法关联：本题是最大子段和问题的变种。若将价格序列转化为每日的利润序列（后一天减前一天），则原问题等价于寻找该利润序列的最大子段和。算法关联8.3.2股票买卖问题问题描述为n=2^k个运动员设计满足特定要求的循环赛日程表。分治策略分解：将n个运动员分成两半。求解：递归为两半运动员设计日程表。合并：根据规律填充整个日程表(A=D,B=C,B=A+n/2)。规律总结日程表可以由左上角的子表通过复制和加法生成。n=4时的日程表规律8.3.3循环赛日程表voidsolve(intn){if(n==1)return;inthalf=n/2;solve(half);//填写左上角for(inti=0;i<half;i++){for(intj=0;j<half;j++)

{arr[i+half][j]=arr[i][j]+half;//填写左下方arr[i][j+half]=arr[i+half][j];//填写右上方arr[i+half][j+half]=arr[i][j];//填写右下方}}}1.分治算法定义：分而治之，将大问题分解为子问题，合并子问题的解。2.适用条件：问题可分解、子问题可合并、子问题独立。3.二分答案：特殊的分治应用，适用于答案有范围且单调的问题。4.典型应用：最大子段和、股票买卖、循环赛日程表。一、选择题1.下列选项中，不属于分治算法特征的是（C）2.分治算法的基本思想是什么（A）二、判断题1.分治算法将一个大问题转化为若干个子问题，然后在子问题的基础上再进行划分，直到能够快速解决一个子问题时停止划分（√）2.分治算法适用于所有类型的问题（×）习题搜索算法概论搜索算法是计算机解题中的“万能解题法”，尤其适用于那些没有有效算法的问题。在本章中，我们将学习搜索的基本概念、深度优先搜索（DFS）、广度优先搜索（BFS）以及重要的回溯法，并通过经典的排列、子集和、迷宫等问题来掌握它们的应用。第9章搜索目录9.1搜索基础9.2回溯法9.3深搜与广搜9.1.1搜索概述定义：一种“万能解题法”，主要用于解决那些没有已知有效算法的问题。定义核心思想：在解空间中进行有组织地枚举，并通过“剪枝”策略避免无意义的搜索，从而显著提高效率。核心思想与暴力枚举的关系：搜索本质上是一种更高效、更有条理的枚举方式，相比暴力枚举减少了大量无效尝试。与暴力枚举的关系9.1.2全排列与解空间树全排列问题：枚举所有可能的排列组合，是理解搜索算法的经典案例。解空间树：解空间的一种树形组织形式，直观展示了解的逐步生成过程与状态空间。剪枝：在搜索过程中，通过约束条件提前判断并放弃不可能得到解的路径，从而大幅减少无效搜索，提高效率。三位数字全排列的解空间树示意图深度优先搜索（DFS）：沿着一条路径尽可能深地搜索，直到尽头再回溯。通常用递归或栈实现。广度优先搜索（BFS）：从根节点开始，“齐头并进”地搜索所有分支。通常用队列实现。回溯法：深搜的一种常见形式，强调“探索与撤销”，通过状态管理来穷举所有可能解。9.1.3深搜、广搜与回溯向前探索，发现错误就退回一步重新选择，反复进行直到找到解。基本思想包含“搜索”和“回溯”两大步骤，核心是“修改→递归→恢复”的三段式结构。算法框架排列组合、图与棋盘问题、人机对弈、决策问题等场景。典型应用9.2.1回溯法概述算法框架：voidSearch(intk)//第k步操作{if(到达目的地){输出解;return;}for(i=1;i<=本步可选方案总数;i++)if(第i种选法能够满足条件) //剪枝{

保存结果 //保存第k步的选择Search(k+1);

//进入第k+1步

回溯 //退回第k步的初始状态

}}问题描述：从n个整数中取出r个进行排列，列出所有可能。解题思路：通过交换元素来选择当前位置的数字（破坏现场），递归处理下一个位置，递归返回后再交换回来（恢复现场）。9.2.2排列问题voidsearch(intk)//参数k表示进行第k步选择{if(k>r)

{输出排列方案；return;}//已经选够了r位数

for(inti=k;i<=n;i++)//选择第k个字符{

swap(a[i],a[k]); //交换元素

search(k+1); //进入下一步

swap(a[i],a[k]); //恢复现场

}}问题描述：找出集合中所有和为给定值W的子集。解题思路：对每个元素，有选与不选两种选择。通过剪枝（左子树剪枝和右子树剪枝）来避免无效搜索。剪枝策略：若已选元素和超过W，则剪去左子树；若剩余元素和不足以达到W，则剪去右子树。子集和问题的解空间树9.2.3子集和问题程序核心代码：回溯法实现子集和问题（含剪枝）voiddfs(inti,intsum1,intsum2){if(i==n){...}//输出满足条件的解并结束if(sum1+w[i]<=W)//左子树剪枝：选择当前元素不超限{

x[i]=1;dfs(i+1,sum1+w[i],sum2-w[i]);}if(sum1+sum2>W)//右子树剪枝：不选当前元素仍有希望{x[i]=0;dfs(i+1,sum1,sum2-w[i]);}}子集和问题程序实现代码说明：1.左子树剪枝：判断加入当前元素后总和是否超过目标值W，若未超过则递归。2.右子树剪枝：判断即使不选当前元素，剩余元素的和加上已选和是否仍大于W，若是则递归。栈（stack）特性：先进后出，常用于实现深度优先搜索（循环方式）。常用操作：push(),pop(),top(),empty()队列（queue）特性：先进先出，常用于实现广度优先搜索。常用操作：push(),pop(),front(),back(),empty()9.3.1STL中的栈与队列9.3.2迷宫类问题问题描述在迷宫中找到从入口到出口的路径。问题分类1.寻找出口：找到任意一条可行路径，DFS和BFS均可。2.寻找最短路径：找到从入口到出口的最短路径，必须使用BFS。迷宫结构示意图问题：给定一个迷宫，求从左上角走到右下角最少需要走多少步？解题思路：使用队列来管理待探索的节点，从起点开始，依次探索其周围的节点，直到找到终点。搜索过程：像水波纹一样，从起点开始，一层一层地向外扩散，确保最先到达终点的路径是最短的。9.3.3广度优先搜索（迷宫最短路径）广度优先搜索迷宫路径过程迷宫最短路径广搜程序实现intbfs(intx,inty){queue<Node>q;q.push({x,y,1});a[x][y]='#';//标记为已访问while(!q.empty())

{Nodenode=q.front();q.pop();

//取队列首元素if(node.x==r&&node.y==c)returnnode.step;

//到达终点for(inti=0;i<4;++i)

//遍历四个方向

{inttx=node.x+f[i][0],ty=node.y+f[i][1];if(tx<1||tx>r||ty<1||ty>c||a[tx][ty]=='#')continue;a[tx][ty]='#';

//将新增的路径点设置为墙，以免重复进入q.push({tx,ty,node.step+1});

//将新增的路径点加入队列}}return-1;

//没有任何路径能到达出口时}迷宫最短路径BFS核心代码问题：给定一个迷宫，寻找从入口到出口的一条路径。解题思路：使用深度优先搜索即可，深搜可以使用递归模式来实现，也可以使用”栈+循环”模式来实现，本处选择使用”栈+循环”模式。9.3.4深度优先搜索搜索过程：while（栈非空）{

if(栈顶元素是出口){

输出路径;

结束;}else{

针对栈顶元素，在其四周寻找一个从未走过并且是“路”的单元格 if(能找到上述单元格)

将其入栈; else

将栈顶元素出栈}深度优先搜索迷宫路径过程（“栈+循环”模式）●搜索基础：解空间树、深搜（DFS）、广搜（BFS）。●回溯法：基本思想、算法框架、排列与子集和问题。●典型应用：使用BFS解决迷宫最短路径问题。●效率关键：剪枝是提高搜索效率的关键。小结第10章动态规划动态规划是一种非常重要的算法设计思想，它通过将复杂问题分解为多个子问题，并利用子问题的解来构建原问题的最优解。在本章中，我们将学习动态规划的基本概念、核心思想，并通过数字金字塔、股票买卖和01背包等经典问题来掌握其应用。10.1动态规划概述10.2典型例题10.301背包问题动态规划（DynamicProgramming，DP）是运筹学的重要分支，核心在于将复杂问题分解为子问题求解，与分治算法既有相似性又有本质区别。10.1动态规划概述引例：数字金字塔问题描述寻找一条从金字塔顶部到底部的路径，使路径上数字的和最大。贪心法的局限性贪心选择可能无法得到最优解，因为它无法证明当前选择是全局最优的。贪心法路径和为50，而最优路径和为62。数字金字塔与贪心法路径对比示意图核心思路：从顶向下分解问题，从底向上合并结果。分解过程：将原问题分解为求从下一行两个位置出发的最大路径和。合并过程：从最底层开始，逐步向上计算每个位置到底部的最大路径和，最终得到顶部的解。数字金字塔的求解过程数字金字塔的分解与合并过程示意图多阶段决策问题：决策过程可分为若干相互联系的阶段，每个阶段需要做出决策。状态：描述某个阶段子问题的变量集合，如dp[i][j]表示从第i行第j列出发的最大路径和。状态转移方程：描述状态之间关系的数学表达式，是动态规划的核心。例如：dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1])。10.1.2重要概念最优子结构：原问题的最优解包含子问题的最优解。这意味着我们可以通过求解子问题的最优解来构建原问题的最优解。无后效性：某阶段的状态一旦确定，后续决策不受之前状态和决策的影响。即未来与过去无关，只取决于当前状态。公共子问题：递归求解时会产生重复的子问题。动态规划通过记录子问题的解（记忆化）来避免重复计算，从而显著提升效率。10.1.3三大特征递归模式：从顶向下分解问题，将复杂的数字金字塔问题拆解为多个子问题，同时使用备忘录（Memoization）记录子问题的解，避免重复计算，提升算法效率。递推模式：从底向上合并结果，利用循环结构从金字塔的底层开始，逐步向上计算每个位置的最优状态值，最终推导出顶层的全局最优解。核心代码：分别实现递归（含备忘录）和递推两种模式的代码逻辑，对比两种实现方式的时间复杂度与空间复杂度差异。10.2.1数字金字塔程序实现10.2.2股票买卖问题问题描述已知n天中每一天股票的价格，在最多允许一次买卖的情况下，计算股票的最大利润。问题描述解题思路遍历每一天的价格，记录到当前为止的最低价格，并计算当前卖出的利润，更新最大利润。解题思路状态定义minPrice：记录最低价格maxProfit：记录最大利润状态定义一、问题描述在背包容量有限的情况下，选择物品装入背包，使总价值最大。这是一个经典的组合优化问题。二、问题分类1.01背包：每件物品只能选一次（要么选，要么不选）。2.完全背包：每件物品可以选无限次。3.多重背包：每件物品有有限的数量限制。10.301背包问题背包问题示意图问题描述：给定物品的重量和价值，以及背包容量，选择物品使总价值最大。解题思路：从最后一个物品开始考虑，对于每个物品，有选和不选两种选择。递归求解这两种选择的最优解，取较大者。分解过程：将问题分解为“选当前物品”和“不选当前物品”两个子问题。背包问题递归解法状态转移方程

：f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i])状态定义：f[i][v]表示前i件物品放入容量为v的背包的最大价值。背包问题递推解法使用递推法的解题过程，相当于在逐行填写如下表格。填写规则：要从第一行开始，从上向下逐行填写。使用f[i][v]代表第i行第v列上单元格的值，其计算公式为：f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i])背包问题递推解法优化在递推法时，计算下一行数据只用到上一行数据，因此可只记录一行数据填写规则：从上向下逐行填写。每一行从右向左逐列填写！计算公式：f[v]=max(f[v],f[v-w[i]]+c[i])核心知识回顾：课堂小结1.动态规划概述：掌握基本概念、核心思想及重叠子问题、最优子结构、无后效性三大特征。2.典型例题：深入理解数字金字塔路径和股票买卖的动态规划解法思路。3.01背包问题：熟悉问题描述，对比递归解法与动态规划的差异，熟练推导状态转移方程以优化空间与时间复杂度。高精度运算概述在编程中，我们经常会遇到超出普通数据类型范围的大整数运算，这时候就需要用到高精度运算。本章将介绍高精度运算的基本概念、数据存储方式，并详细讲解高精度加减乘除的实现方法。第11章高精度运算11.1高精度运算概述11.2高精度加法11.3高精度减法11.4高精度乘法11.5高精度除法目录11.1.1什么是高精度运算（1）核心概念：定义处理超出普通数据类型（如int、longlong）表示范围的大整数运算，也称为大整数运算。（2）应用场景：必要性当数值超过普通数据类型的存储极限时，语言内置类型无法准确表示，必须手动实现存储和运算逻辑。（3）存储极限：longlong范围-9223372036854775808～9223372036854775807（3）数值界限11.1.2高精度数据的存储输入方式：通常采用字符串方式输入，以避免数值溢出问题。存储方式：将字符串逐位转换为数字存入数组，并逆序存储（低位在前，高位在后），便于运算时的个位对齐。高精度数据的存储示意图1.高精度与高精度运算：两个数都是高精度数，运算过程需要完全模拟手工计算。2.高精度与低精度运算：一个数是高精度数，另一个数是普通数据类型（如int）。3.区别与优势：高精度与低精度运算可以利用编程语言的内置运算功能，实现逻辑相对简单。11.1.3二类高精度运算11.2.1高精度加高精度原理：完全模拟手工加法，从个位开始逐位相加，并处理低位向高位的进位。步骤：遍历两个数组，对应位相加，计算进位，处理最高位的进位。高精度加法原理示意图1.字符串转数组：将输入的大数字符串逆序存储到整型数组中，以便从低位到高位进行运算。2.逐位相加：遍历两个数组，对应位相加，加上低位的进位值。3.处理进位：计算当前位的和，保留个位作为当前结果，十位作为新的进位传递到高位。4.结果输出：逆序输出结果数组，得到最终的高精度加法结果。高精度加高精度程序实现要点11.2.2高精度加低精度原理：将低精度数加到高精度数的个位上，而后不断向前进位即可。示例：以“987+556”为例，我们将“987”视为高精度数，首先将它的各位数字分离并存储至数组，结果为：a[0]=7，a[1]=8，a[2]=9。计算步骤：将a[0]加上556，得到563，扣除进位值56，得a[0]=3。将a[1]加上进位值56，得到64，再扣除向上的进位值6，得a[1]=4。将a[2]加上进位值6，得a[2]=15。比较两个数的大小，确保被减数大于等于减数。若不满足，需交换并记录负号。（1）比较大小从个位开始逐位相减，若当前位不够减，则向高位借位，借1当10。（2）借位处理计算完成后，去除结果中多余的前导零，以得到正确的数值表示。（3）处理前导零11.3.1高精度减高精度1.比较大小：首先比较两个数的长度和每一位数字，确定被减数是否大于等于减数，若否，则交换并记录结果符号。2.逐位相减：从最低位（个位）开始，对应位数字相减。若本位被减数小于减数，则向高位借位（借1当10），再进行减法运算。3.借位处理：处理借位对高位的影响，确保每一位计算的准确性。4.结果输出：删除结果数组中多余的前导零，然后从高位到低位输出最终结果。高精度减高精度程序实现要点11.3.2高精度减低精度要点将高精度数的个位减去低精度数，然后不断从低位向高位借位，直到每一位数字都>=0。一、算法原理模拟手工乘法过程，用乘数的每一位去乘被乘数的每一位，并将结果累加到正确的位置，最后统一处理进位。二、核心要点结果的位数最多为两个乘数位数之和。a[i]*b[j]的结果应累加到c[i+j]的位置。11.4.1高精度乘高精度高精度乘法过程示意图高精度乘高精度程序实现核心逻辑：使用双重循环模拟手工乘法。外层循环遍历乘数的每一位，内层循环遍历被乘数的每一位。每次相乘的结果累加到结果数组的对应位置，最后统一处理进位并输出。

for(inti=0;i<len1;i++)//乘法遵循交换律，不区分被乘数与乘数 { intx=0; //用于存放进位 for(intj=0;j<len2;j++) { c[i+j]+=a[i]*b[j]+x;//原有内容+当前乘积+进位 x=c[i+j]/10; c[i+j]%=10; } c[i+len2]=x; //结果中最高位向前的进位 }高精度乘高精度核心代码逻辑11.4.2高精度乘低精度【原理】详见课本，以一个具体数字为：987*56=（900+80+7）*56=900*56+80*56+7*56=55272图示如下：高精度乘以低精度运算过程示意图11.5.1高精度除以低精度【原理】模拟手工除法的计算过程，从被除数的高位开始，逐位进行除法运算，同时记录每一步的商和余数。【要点】被除数需按原顺序存储（高位在前），因为除法运算的逻辑是从高位向低位依次进行的。高精度除以低精度运算过程示意图课堂小结●高精度运算概述：定义、数据存储方式（字符串输入，数组逆序存储）。●高精度加法：模拟手工加法，处理进位。●高精度减法：模拟手工减法，处理借位和大小比较。●高精度乘法：模拟手工乘法，处理结果位置和进位。●高精度除法：模拟手工除法，从高位开始，处理商和余数。第12章图论算法图论是算法领域的一个重要分支，它研究的是由顶点和边构成的图的性质和应用。本章将介绍图的基本概念、存储结构、遍历方法以及经典的最短路径算法。算法基础目录12.1图论入门12.2图的遍历12.3最短路径12.4最小生成树12.5拓扑排序12.1.1基本概念图的定义：图是由一组顶点（V）和连接这些顶点的边（E）组成的数据结构，graph=(V,E)。有向图与无向图：边有方向的图称为有向图；边没有方向的图称为无向图。权值：边的权重，例如距离、费用等。带权值的图称为有权图。有向图与无向图示意图一、顶点的度在无向图中，顶点的度是指与该顶点相连的边的数量。在有向图中，分为入度（指向该顶点的边数）和出度（从该顶点出发的边数）。二、连通性图中任意两个顶点之间是否存在路径。如果任意两点都有路径，则为连通图；否则为非连通图。12.1.1基本概念连通图与非连通图示意图12.1.2图的存储结构（1）邻接矩阵法邻接矩阵：使用二维数组存储图，G[i][j]表示顶点i和顶点j之间边的权值。若两点间无边，则权值通常记为0或∞。特点：实现简单，判断任意两点间是否存在边的时间复杂度为O(1)；但空间复杂度为O(V²)（V为顶点数），比较耗费空间，因此更适合边数较多的稠密图。无向图及其邻接矩阵12.1.2图的存储结构（2）邻接表法邻接表：为每个顶点建立一个链表，存储与该顶点相连的边。它结合了顺序存储和链式存储的特点，是图的一种重要存储方式。核心特点：1.空间效率高，空间复杂度为O(V+E)；2.特别适合存储稀疏图（边数远小于顶点数）；3.遍历顶点的所有邻接边非常方便快捷。无向图及其邻接表存储示意1.概念从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次。2.特点不遗漏、不重复地访问所有顶点；3.实现要点为了避免重复访问某个顶点，可以设置一个标志数组：boolvisited[n]; 4.遍历方式深度优先遍历和广度优先遍历二种。12.2.1图的遍历1.算法思想从起始顶点出发，沿着一条路径尽可能深地访问未访问的邻接顶点，直到无法继续，然后回溯，尝试其他路径。核心是“先走到底，再回头”。2.实现方案通常采用递归实现，也可通过栈（Stack）模拟递归过程。12.2.2深度优先遍历（DFS）深度优先遍历示意图核心代码实现：boolvisited[n]; //标志数组voiddfs(inti)//深度优先遍历，采用递归形式

{visited[i]=true;cout<<char('1'+i)<<"";//输出顶点i上的文字

for(intj=0;j<n;j++)//扫描邻接矩阵的第i行

if(G[i][j]!=0&&!visited[j])dfs(j);}深度优先遍历程序实现intmain(){//将每个顶点都作为起点来启动一次遍历for(inti=0;i<n;i++)

if(!visited[i])dfs(i);return0;}

策略：贪心策略类型：单源最短路径限制：无负权边Dijkstra算法策略：动态规划类型：单源最短路径特点：可处理负权边，能检测负权环Bellman-Ford算法策略：动态规划类型：多源最短路径特点：时间复杂度高O(V³)，可处理负权边（无负权环）Floyd算法12.3.1最短路径概述Floyd算法问题定义：寻找图中两顶点之间的最短路径，路径权重可以代表距离、时间、费用等。12.3.2Dijkstra算法▍算法思想采用贪心策略，从源点开始，每次选择距离源点最近的未确定顶点，加入已确定集合，并更新其邻接顶点的距离。▍适用场景解决单源最短路径问题。注意：图中不能有负权边，否则算法可能失效。Dijkstra算法执行过程示意（完整图形见课本）核心代码实现逻辑：Dijkstra算法的代码实现需维护三个关键数组：distance[]：记录源点到各顶点的当前最短距离，初始时源点距离为0，其余为无穷大。pre[]：记录路径的前驱节点，用于最终回溯输出最短路径。known[]：标记顶点是否已确定最短路径，避免重复处理。算法核心循环中，每次从未确定的顶点中选择距离源点最近的顶点，标记为已确定；随后遍历其所有邻居节点，通过“松弛操作”更新邻居的最短距离和前驱信息，直至所有顶点处理完毕。Dijkstra算法程序实现12.3.3Floyd算法核心思想：基于动态规划思想，通过三重循环，依次将每个顶点作为中转点，不断更新任意两点间的最短距离。算法思想特点与场景：适用于多源最短路径问题。可处理负权边（无负权环）。代码简洁，但时间复杂度较高（O(V³)）。适用场景核心优势：无需指定源点，直接计算任意两点间的最短路径。实现简单，仅需一个距离矩阵和三重循环即可完成。核心优势核心代码实现：for(intk=1;k<=n;k++) //算法核心，以第k个顶点为中间点进行松驰for(inti=1;i<=n;i++)

for(intj=1;j<=n;j++)

if(e[i][j]>e[i][k]+e[k][j])e[i][j]=e[i][k]+e[k][j];算法解析：外层循环遍历所有可能的中转点k，内层两层循环遍历所有顶点对(i,j)。通过不断松弛