单源最短路
单源最短路问题是图论中的核心问题之一，在许多领域都有广泛应用.
定义
单源最短路问题是指在一个带权图（可以是有向图或无向图）中，给定一个特定的源点，求解从该源点到图中其余所有顶点的最短路径长度以及具体路径。图中的每条边都被赋予一个权值，这个权值通常代表着距离、时间、成本等实际意义上的度量值。该问题的目标就是找出从源点出发，到其他各个顶点的所有可能路径中，权值总和最小的路径。
常见算法
迪杰斯特拉（Dijkstra）算法
基本思想：从源点开始，采用贪心策略，逐步扩展并确定到其他顶点的最短距离。算法会维护一个距离集合，每次选择当前距离源点最近且未被处理过的顶点，然后利用这个顶点去更新其邻接顶点的距离，直到所有顶点都被处理完毕。
适用场景：适用于所有边权值非负的图。比如在地图导航中，若用边权表示实际路程距离，由于距离不会是负数，就可以使用该算法来计算最短行车路线。
时间复杂度：一般实现的时间复杂度为O(V^2)，其中V是图中顶点的个数。若使用堆等数据结构进行优化，时间复杂度可降为O((V + E)logV)，E是边的数量。
贝尔曼福特（BellmanFord）算法
基本思想：通过对图中的所有边进行多次松弛操作来逐步逼近最短路径。所谓松弛操作，就是尝试通过其他顶点来更新当前顶点到源点的距离，如果新的路径更短，则更新距离值。算法最多需要进行V 1次松弛操作，其中V是顶点数。
适用场景：适用于存在负权边的图，但不能处理存在负权回路的图。例如在金融领域，若用边权表示汇率变化，可能会出现负权边，此时贝尔曼 福特算法就可以发挥作用。
时间复杂度：时间复杂度为O(VE)，其中V是顶点数，E是边数。
弗洛伊德沃肖尔（FloydWarshall）算法
基本思想：运用动态规划的思想，通过考虑所有可能的中间顶点来更新任意两点之间的最短路径。它会依次将每个顶点作为中间节点，检查通过该中间节点是否能使其他两点之间的路径更短，从而不断更新最短路径矩阵。
适用场景：主要用于求任意两点之间的最短路径，虽然也能解决单源最短路问题，但一般在需要大量查询不同源点的最短路径问题时使用更频繁。比如在社交网络分析中，要计算任意两个用户之间的最短关系路径，就可以使用该算法。 时间复杂度：时间复杂度为O(V^3)，其中V是顶点数。
SPFA（Shortest Path Faster Algorithm）算法
基本思想：SPFA算法是对贝尔曼福特算法的一种优化，它利用队列来存储待松弛的顶点。首先将源点加入队列，然后不断取出队首顶点，对其邻接顶点进行松弛操作，如果某个邻接顶点的距离值被更新，且该顶点不在队列中，则将其加入队列。重复这个过程，直到队列为空。
适用场景：在存在负权边的图中表现较好，并且在稀疏图上性能更优。例如在一些网络流问题中，若边权存在负数且图结构较为稀疏，SPFA算法能高效地求出最短路径。
时间复杂度：在一般情况下，SPFA算法的时间复杂度为O(kE)，其中k是一个常数，E是边数。在最坏情况下，时间复杂度会退化为O(VE)，与贝尔曼 福特算法相同，但在很多实际应用中，它的运行效率要比贝尔曼 福特算法高很多。
应用场景
交通与导航领域：在城市交通网络中，可计算从一个地点到其他所有地点的最短驾车距离或公交出行最短路径等，为人们提供出行路线规划，如百度地图、高德地图等导航软件就是利用此类算法为用户规划最佳出行路线。
通信网络优化：在计算机网络中，确定从一个节点到其他节点的最短数据传输路径，以优化数据传输路径，减少传输延迟，提高网络通信效率。 物流配送规划：物流企业可依据单源最短路算法，规划从仓库到各个送货地点的最短路线，从而降低运输成本，提高配送效率，合理安排物流资源。
项目管理与调度：在项目管理中，可用于确定从项目开始节点到其他各个任务节点的最短时间路径，帮助项目管理者找出关键路径，合理安排任务顺序和时间，确保项目按时完成。
习题1（热浪）：
分析：
背景：这道题目设定了一个实际生活场景，即得克萨斯州民众遭受热浪，农夫John要从威斯康星运送牛奶到得克萨斯州。在运输过程中，存在由多个城镇和连接城镇的道路组成的交通网络，每条道路都有相应的通过费用。这种场景类似于现实中的物流运输、资源调配等情况，在这些实际问题中，人们常常需要找到从一个起始地点到目标地点的最低成本路线，对应到数学模型中，就是图论里的单源最短路问题。
解题思路
构建图模型：把每个城镇当作图中的顶点，编号从(1)到(T)。连接两个城镇的道路视为图中的边，边的权值就是道路的通过费用(C_i) 。这样就将实际的城镇道路网络抽象成了一个带权图。
选择合适算法： 由于题目未提及存在负权边，优先考虑迪杰斯特拉算法。它基于贪心策略，从起始城镇(T_s)（源点）出发，不断选择距离源点最近的未确定顶点，更新其邻接顶点的距离，逐步确定到其他所有顶点的最短距离，最终得到到终点城镇(T_e)的最短路径和最小总费用。 若后续发现可能存在负权边，那就需要使用能处理负权边的算法，比如SPFA算法或者贝尔曼 福特算法。SPFA算法利用队列优化，通过不断松弛顶点来更新最短距离；贝尔曼 福特算法则是对图中所有边进行(V 1)次松弛操作（(V)为顶点数）来求解最短路径。 实现算法求解：按照选定算法的逻辑，在构建好的图上进行计算，找到从起始城镇(T_s)到终点城镇(T_e)的最短路径，路径上的边权总和就是最小的总费用。
伪代码：
回忆常用的最短路算法来解决这个题目：
floyd：
朴素迪杰斯特拉：
堆优化迪杰斯特拉:
贝尔曼福德算法：
SPFA算法：
习题2（信使）：
分析：
背景：
题目构建了一个战争时期的信息传递场景。前线有多个哨所，哨所之间存在通信联系，且传递信息需要一定时间。指挥部位于第一个哨所，下达命令后通过信使向相连哨所送信，各哨所收到信后也会继续向其他哨所传递，直到所有哨所都收到命令。这种场景类似于现实中网络信息传播、物流配送路线规划等，需要在具有连接关系的节点（哨所）间，以最短的时间完成某种 “任务”（信息传递），可转化为图论相关问题进行求解。
解题思路：
构建图模型：将每个哨所看作图中的一个顶点，哨所之间的通信联系视为图中的边，边的权值为信使在两个哨所间传递信息所需的时间。这样就把哨所网络抽象成了一个带权图。
选择算法：这本质上是求从第一个哨所（源点）到其他所有哨所的最短时间，属于单源最短路问题。可选用迪杰斯特拉（Dijkstra）算法，因为信息传递时间（边权）必然是非负的。该算法通过不断选择距离源点最近且未确定最短时间的哨所，更新其邻接哨所的距离（所需时间），逐步确定到所有哨所的最短时间。
算法实现：使用优先队列（堆）来优化迪杰斯特拉算法，以提高查找和更新的效率。初始时，第一个哨所到自身的时间为 0，到其他哨所的时间设为无穷大。然后不断从优先队列中取出时间最短的哨所，更新其邻接哨所的时间，直到所有哨所都被处理过。
获取结果：最终得到的各哨所到第一个哨所的最短时间中，最大值就是完成整个送信过程所需的最短时间。
伪代码：
习题3（香甜的黄油）：
分析：
背景：
题目描述了农夫 John 为制作出能卖好价钱的超甜黄油，打算利用奶牛喜欢舔糖的习性，通过训练奶牛在听到铃声后前往特定牧场，然后在该牧场放置糖来吸引奶牛，以便晚上挤奶的场景。已知每只奶牛所在的牧场以及牧场之间的路线，需要找出一个合适的牧场放置糖，使得所有奶牛到达该牧场的路程总和最短。这类似于现实生活中的选址优化问题，如物流中心选址，要考虑让各个供货点或收货点到物流中心的总运输距离最短。
解题思路;
构建图模型：把每个牧场看作图中的顶点，牧场之间的路线视为图中的边，边的权值为两个牧场之间的距离。这样就将牧场和路线的实际场景抽象为一个带权图。
计算每个牧场作为目标点的总路程：
对于每个牧场，都将其当作可能放置糖的目标牧场，然后使用单源最短路算法（如迪杰斯特拉算法，因为牧场间距离必然非负），分别计算出其他奶牛所在牧场到该目标牧场的最短距离。
把每头奶牛到目标牧场的最短距离相加，得到所有奶牛到该目标牧场的路程总和。
找出最优解：遍历完所有牧场后，比较得到的各个路程总和，其中数值最小的对应的牧场，就是能使所有奶牛到达的路程和最短的牧场，也就是农夫 John 应该放置糖的牧场。
查看可行的算法的时间复杂度来选择最终的算法：
伪代码：
习题4（最小花费）：
分析：
背景
题目设定了一个关于人际转账的场景，在(n)个人中，部分人之间存在可互相转账的关系，且不同人之间转账手续费不同。需要解决的问题是，在这种情况下，计算出(A)为了让(B)最终收到(100)元，最少要转出多少钱。这类似于实际生活中的金融转账场景，考虑手续费后计算原始转账金额，也与图论中的路径问题相关联，因为要考虑通过不同的转账路径来达到最小支出的目的。
解题思路
1. 构建图模型：将每个人看作图中的一个顶点，可互相转账的两人之间用边连接。边的权值不再是传统意义上的距离等，而是转账的手续费率，比如边权为(z)，表示从一个顶点转账到另一个顶点时，需要扣除转账金额的(z%)作为手续费。
2. 转换问题：为了让(B)收到(100)元，设(A)转出的金额为(x)元，那么经过一系列转账路径后，最终到达(B)的金额为(x)扣除所有手续费后的剩余金额，要使其等于(100)元。我们可以将其转化为求从顶点(A)到顶点(B)的“费用最小”路径问题，这里的“费用”指的是为了让(B)最终得到(100)元，(A)初始需要转出的金额。
3. 选择算法：使用单源最短路算法的变形来求解，例如迪杰斯特拉算法的变体。由于手续费率是非负的（(z < 100)），可以基于贪心策略，从(A)点出发，逐步找到到其他各点使得最终能让目标点收到指定金额（这里是(B)收到(100)元）的最小初始转账金额。在计算过程中，根据边权（手续费率）来更新到达各个顶点的“费用”。
4. 计算结果：当算法运行结束后，得到的从(A)到(B)的“费用”，就是(A)最少需要转出的钱数，使得(B)最终能收到(100)元。
伪代码：
习题5（最优乘车）：
分析：
这道题可通过对最短路算法进行变形来求解
构建图模型 把每个巴士站视为图的顶点，编号从1到N。对于每条单程巴士线路，将线路中相邻的巴士站用有向边连接。例如，若有一条巴士线路经过站点A、B、C，就添加从A到B、B到C的有向边。这里边的权值不再是距离等常规概念，而是设定为1，表示一次乘车过程。如果在同一站台能换乘不同线路的巴士，就相当于这些线路对应的边在该站台顶点处相互连接。
选择算法 特殊的最短路算法（在无权图中求最短路径）。因为本题要求的是换乘次数最少，也就是经过的边数最少，而BFS能按照距离起始点由近到远的顺序遍历图中的顶点，符合求解最少换乘次数的需求。
最短路算法选择
由于本题要求的是换乘次数最少，也就是经过的边数最少，迪杰斯特拉（Dijkstra）算法和广度优先搜索（BFS） 都可以解决该问题。但考虑到本题边权都为 1 的特殊性，BFS 算法更为合适，因为它可以在无权图（或者边权都为 1 的图）中更高效地找到最短路径。不过这里也可以使用迪杰斯特拉算法来统一使用最短路算法的思路。
伪代码：
习题6（昂贵的聘礼）：
分析：
该题设定在一个具有等级限制和交易规则的印第安部落场景中。探险家为娶酋长女儿，面临不同物品交易条件及等级限制，需综合各种物品的价格、等级、替代品等信息，以求出最少的金币花费。将其转化为图论问题，每个物品可看作图中的节点，交易关系和价格差异构成边，等级限制则是约束条件，目标是通过虚拟节点的最短路算法找到从初始状态到获得 “酋长的允诺”（编号 1 物品）的最短路径（即最少花费）。
伪代码：
