《单源最短路算法及其应用》
- 格式：ppt
- 大小：680.00 KB
- 文档页数：35
下载文档原格式
合集下载
062单源最短路径问题及算法
祝女儿18岁生日说说祝女儿18岁生日说说 1 、十八岁有火一样的激情，它的能量可以把高山熔铸成利剑，它的光芒可与日月同晖，在宇宙中与天地共享生命的崇高。
2 、送你一首十八岁生日歌，祝你今天最快乐。
福神为你当陪客，寿星帮你把面做。
财神送你红包了，喜神专为你唱歌。
幸运女神是你姐，所有烦恼全消灭。
3 、在你十八岁成人之际，如果说我们对你还有什么更多的期望，那就是希望你永远不要丢掉自己身上那些美好的品德，并且能够不断地完善自己。
在你成长的岁月中，我们对你有过很多的批评和责备，甚至有一些过分的苛求，但那都是因为我们对你抱有更多的期望，希望你能够更优秀、更完美。
4 、生活可以平淡，犹如蓝天下宁静的湖水。
生活也可以是诗，在一路的奔腾中高歌。
只要我们时常惦记彼此，我想：再苦、再累的每个日子都将是幸福。
十八岁生日快乐！5 、十八岁了，十八岁了。
无数句疑问，只化作了一句直冲云霄的呼喊十八岁，你好。
6 、十八岁，花一般的年龄，梦一样的岁月，愿你好好地把握，好好地珍惜，给自己创造一个无悔的青春，给祖国添一份迷人的风景！7 、十八岁有火一样的激情，它的能量可以熔化高山，它的光芒可与日月同辉，在宇宙中与天地共享生命的崇高，自然的博大。
8 、我们相识了这么久，很高兴我们的友情依然如故，这样美丽，这样纯洁，难忘你娇艳的笑容，难忘你快乐的模样，我们的真情永不改变，祝你十八岁生日快乐！9 、我为你建造一座美丽的花园，那里种满了幸福的花朵，铺满了吉祥的绿草。
今天是你的十八岁生日，我还特地为你你挂满了快乐的云彩。
愿你事事顺意，天天舒心。
1 0 、十八岁路还长，可能真正属于自己撵也撵不走的一些东西还没有遇到而已，何必给自己的心情过不去呢。
1 1 、十八年来，在养育你的路上，作为父亲，有很多的失误和不足，希望你理解，因为我也是人，是一个普普通通的男人，但爱你的心从来没有动摇和改变。
1 2 、十八岁，无论成功与失败，都是对我们成长的帮助，珍惜十八，珍惜阳光，珍惜岁月。
单源最短路
• 这道题是一道比较简单的求单源最短路的 问题
• 可以用dijkstra算法spfa算法等解决 • 可以用来练习熟悉一些最短路算法
SPFA算法
• 我们用数组d记录每个结点的最短路径估计值，而 且用邻接表来存储图G。我们采取的方法是动态 逼近法： 设立一个先进先出的队列用来保存待优化的结 点，优化时每次取出队首结点u，并且用u点当前 的最短路径估计值对离开u点所指向的结点v进行 松弛操作，如果v点的最短路径估计值有所调整， 且v点不在当前的队列中，就将v点放入队尾。这 样不断从队列中取出结点来进行松弛操作，直至 队列空为止。
Usaco Butter（usaco）
• 分析：
•
首先分析题目，把一个个农场可以抽象为一个个点，
把一条条路抽象为连接两点的一条条边，我们便得到了一
张图。
• 根据题目的意思，实际就是选择一个顶点，使得从该点到 给定的N个顶点的权值之和最小。
• 由于每一个顶点（及农场里）不只有一头牛，所以用邻接 表更加方便。第一组的结点， 灰色的结点为第二组的结点
1808
∞11394
0
5
∞77
Dijkstra算法的执行速度取决于优先队列的数据结构
1、用一维数组来实现优先队列Q=V-S：算法运行时 间为O(V2+E)=O(V2)。
2、用二叉堆来实现优先队列Q：算法运行时间为 O((V+E)lgV)。通常情况下，边数|E|都不小于顶点数 |V|，所以运行时间又可以简化为O(ElgV)。
SPFA算法
• 适用条件: 任意边权为实数的图 • 定理: 只要最短路径存在，上述SPFA算法必定能
求出最小值。
• 证明：每次将点放入队尾，都是经过松弛操作达 到的。换言之，每次的优化将会有某个点v的最短 路径估计值d[v]变小。所以算法的执行会使d越来 越小。由于我们假定图中不存在负权回路，所以 每个结点都有最短路径值。因此，算法不会无限 执行下去，随着d值的逐渐变小，直到到达最短路 径值时，算法结束，这时的最短路径估计值就是 对应结点的最短路径值。（证毕）
单源次短路径
单源次短路径
（原创实用版）
目录
1.单源最短路径的定义
2.单源最短路径的算法
3.单源最短路径的应用实例
正文
一、单源最短路径的定义
在图论中，单源最短路径是指从指定的源节点到图中其他所有节点的最短路径。
这里的最短路径是指路径长度最短，即经过的边数最少。
对于有向图来说，单源最短路径可能存在多个，而对于无向图来说，单源最短路径是唯一的。
二、单源最短路径的算法
求解单源最短路径的经典算法是 Dijkstra 算法和 Floyd 算法。
1.Dijkstra 算法
Dijkstra 算法是一种贪心算法，它每次选择距离源节点最近的节点进行扩展，直到到达目标节点。
算法的基本思想是每次将源节点到当前已扩展节点的距离与源节点到其他未扩展节点的距离进行比较，选出距离最近的节点进行扩展。
扩展的过程中，需要将已扩展的节点的距离更新为新扩展的节点的距离。
2.Floyd 算法
Floyd 算法是一种动态规划算法，它通过计算源节点到其他所有节点的距离，来确定最短路径。
算法的基本思想是：对于每个节点 i，我们尝试将其他所有节点作为中间节点，看看是否能够从源节点到达该节点，如果能够到达，我们就更新该节点到其他节点的距离。
三、单源最短路径的应用实例
单源最短路径在实际生活中有很多应用，比如：
1.最短路径导航：在导航系统中，我们需要从起点到终点规划出一条最短路径，以便为用户提供最佳的行驶路线。
2.物流配送：在物流配送中，我们需要从仓库到各个配送点规划出一条最短路径，以便为顾客提供最快的配送服务。
算法合集之《最短路算法及其应用》
11
SPFA算法
我们用数组d记录每个结点的最短路径估计值，而且用邻接表 来存储图G。我们采取的方法是动态逼近法：
设立一个先进先出的队列用来保存待优化的结点，优化时每次 取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向 的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点 不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点 来进行松弛操作，直至队列空为止。
定义
在最短路问题中，给出的是一有向加权图 G=(V,E)，在其上定义的加权函数W:E→R为从 边到实型权值的映射。路径P=(v0, v1,……, vk) 的权是指其组成边的所有权值之和：
w( p)
w(v
i 1
k
i 1
, vi )
定义u到v间最短路径的权为：
v)
minw( p ):u v 如果存在由u到v的通路 如果不存在
14
在最短路径表中，e，g的最短路径估值又变小，队列中无e点，e入队，队列 中存在g这个点，g不用入队，此时队列中元素为g，e 队首元素g点出队，对以g为起始点的所有边的终点依次进行松弛操作（此 处只有b点），此时路径表格状态为：
a d[i] 0
b
c
d
e
f
g 14
17 8
15 13 11
在最短路径表中，b的最短路径估值又变小，队列中无b点，b入队，此时队列 中元素为e，b
推论
推论1.1 给定有向加权图G=(V,E),源点为s，则对 于所有边(u,v) E，有：
(s, v) (s, u) w(u, v)
证明： 从源点s到结点v的最短路径P的权不大于 从s到v的其它路径的权。特别地，路径P的权也不大 于某特定路径的权，该特定路径为从s到u的最短路径 加上边(u,v)。（证毕）
SPFA算法
我们用数组d记录每个结点的最短路径估计值，而且用邻接表 来存储图G。我们采取的方法是动态逼近法：
设立一个先进先出的队列用来保存待优化的结点，优化时每次 取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向 的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点 不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点 来进行松弛操作，直至队列空为止。
定义
在最短路问题中，给出的是一有向加权图 G=(V,E)，在其上定义的加权函数W:E→R为从 边到实型权值的映射。路径P=(v0, v1,……, vk) 的权是指其组成边的所有权值之和：
w( p)
w(v
i 1
k
i 1
, vi )
定义u到v间最短路径的权为：
v)
minw( p ):u v 如果存在由u到v的通路 如果不存在
14
在最短路径表中，e，g的最短路径估值又变小，队列中无e点，e入队，队列 中存在g这个点，g不用入队，此时队列中元素为g，e 队首元素g点出队，对以g为起始点的所有边的终点依次进行松弛操作（此 处只有b点），此时路径表格状态为：
a d[i] 0
b
c
d
e
f
g 14
17 8
15 13 11
在最短路径表中，b的最短路径估值又变小，队列中无b点，b入队，此时队列 中元素为e，b
推论
推论1.1 给定有向加权图G=(V,E),源点为s，则对 于所有边(u,v) E，有：
(s, v) (s, u) w(u, v)
证明： 从源点s到结点v的最短路径P的权不大于 从s到v的其它路径的权。特别地，路径P的权也不大 于某特定路径的权，该特定路径为从s到u的最短路径 加上边(u,v)。（证毕）
单源最短路径算法在导航中的应用
单源最短路径算法在导航中的应用随着科技的发展，我们越来越离不开导航。
不管是在出行时还是旅游时，导航都可以给我们带来很大的便利。
而在导航中，单源最短路径算法起着重要的作用。
本文将介绍单源最短路径算法的原理及在导航中的应用。
一、单源最短路径算法原理单源最短路径算法是指，从图中的一个节点出发，求到达图中其他节点的最短路径。
其中，最短路径可以用边的权值来表示。
常用的单源最短路径算法有迪杰斯特拉算法和贝尔曼-福德算法。
1.迪杰斯特拉算法迪杰斯特拉算法是一种用于解决带权有向图或无向图中单源最短路径问题的算法。
该算法通过每次找到未确定最短路径中距离最小的节点，逐步确定从源节点到其他节点的最短路径。
具体操作如下：1) 初始化将源节点到其他节点的距离为无穷大，源节点到自身距离为0；2) 选择源节点为第一个待确定最短路径的节点；3) 以该节点为起点，计算所有由该节点出发的路径长度并更新距源节点的最短距离，标记该节点为已确定最短路径；4) 从剩余未确定最短路径的节点中选择距离源节点最近的节点作为下一个待确定最短路径的节点，重复步骤3和4，直至所有节点都已被标记为已确定最短路径。
2.贝尔曼-福德算法贝尔曼-福德算法是一种解决带权有向图中单源最短路径问题的算法。
该算法通过边的松弛操作，逐步缩小最短路径的范围。
具体操作如下：1) 初始化源节点到所有其他节点的距离为无穷大，源节点到自身距离为0；2) 按照边的顺序，对于每条边(u,v)，计算源节点到v的距离，如果该距离比已知的最短距离要小，则更新最短距离；3) 重复步骤2，直至所有最短距离已经稳定不变。
二、在导航中，单源最短路径算法可以用于求出两个地点之间的最短路径。
通常情况下，我们可以将地图表示成一个图，各个路口和交叉口表示图的节点，道路表示图的边，各个地点之间的距离可以表示为边的权值。
然后选中出发点，利用单源最短路径算法求出到其他节点的最短距离即可。
而单源最短路径算法在导航中可以应用于以下几个方面。
单源最短路径计算机算法设计与分析
单源最短路径计算机算法设计与分析在单源最短路径问题中，给定一个带权重的有向图G=(V,E)，其中V表示顶点集，E表示边集，每条边（u，v）的权重表示从顶点u到顶点v的距离或成本。
我们需要找到从源节点s到图中其他所有节点的最短路径。
目前有多种经典的单源最短路径算法，包括迪杰斯特拉算法、贝尔曼-福特算法和弗洛伊德算法。
迪杰斯特拉算法是一种广泛使用的单源最短路径算法。
该算法使用了一种贪心的策略，从源节点开始，依次计算源节点到所有其他节点的最短路径。
算法维护一个距离数组d[]，表示源节点到各个节点的最短距离。
初始时，设置源节点的最短距离为0，其他节点的最短距离为无穷大。
接下来，迭代地选择一个距离源节点最近的节点，更新该节点到其他节点的距离。
当所有节点都被选取时，算法终止。
迪杰斯特拉算法的时间复杂度为O(V^2)，可以通过优先队列等数据结构进行优化，达到O(ElogV)。
贝尔曼-福特算法是另一种常见的单源最短路径算法。
该算法使用了一种动态规划的策略，通过逐步增加路径长度的方式，计算源节点到其他节点的最短路径。
算法维护一个距离数组d[]，表示源节点到各个节点的最短距离。
初始时，将所有节点的最短距离设置为无穷大，将源节点的最短距离设置为0。
接下来，迭代地对边集中的每条边进行松弛操作，即尝试通过该边缩短从源节点到目标节点的距离。
重复上述操作V-1次后，所有节点的最短距离就会得到更新。
贝尔曼-福特算法的时间复杂度为O(VE)，其中V和E分别表示节点和边的数量。
弗洛伊德算法是一种用于计算所有节点对之间最短路径的算法，也可以用于单源最短路径计算。
该算法使用了一种动态规划的策略，通过逐步增加经过的中间节点的数量，计算节点对之间的最短路径。
算法维护一个距离矩阵d[][]，其中d[i][j]表示节点i到节点j的最短距离。
初始时，将矩阵中的元素设置为边的权重。
接下来，迭代地对每个节点k进行考虑，更新所有节点对之间的最短距离。
单源点最短路径
单源点最短路径单源点最短路径是图论中的一种重要问题，用于寻找从一个特定节点到其他节点的最短路径。
在实际应用中，这个问题很常见，比如用于导航系统、通信网络、物流配送等领域。
下面将介绍单源点最短路径的定义、算法和应用。
需要明确单源点最短路径的定义。
在一个有向带权图中，每个边都有一个权重和方向。
单源点最短路径问题的目标是找到从给定的源节点s到所有其他节点的最短路径。
路径的长度由边的权重之和来衡量。
最短路径可能不唯一，但它们的长度必定是最小的。
接下来介绍两种经典的单源点最短路径算法：Dijkstra算法和Bellman-Ford算法。
Dijkstra算法是一种贪心算法，用于解决带权有向图的单源点最短路径问题。
它的基本思想是从源节点开始，逐层扩展，选择距离源节点最近的节点作为下一个中转节点。
通过动态维护一个距离数组，记录每个节点到源节点的当前最短路径长度，逐步更新和计算最短路径。
具体步骤如下：1.创建一个距离数组dist[]，用于记录每个节点到源节点的当前最短路径长度。
初始化dist[]为无穷大，源节点的距离为0。
2.创建一个集合sptSet[]，用于记录已经找到最短路径的节点。
初始化sptSet[]为空集合。
3.依次选择未加入sptSet[]的节点中距离源节点最近的节点u，并将u加入sptSet[]。
4.对于u的每个邻居节点v，如果经过u到v的路径长度dist[u]+weight(u,v)比dist[v]更小，则更新dist[v]。
5.重复步骤3和步骤4，直到最短路径全部找到。
Bellman-Ford算法是一种动态规划算法，用于解决带权有向图的单源点最短路径问题。
它通过迭代更新距离数组dist[]，直到每个节点的最短路径长度不再改变，或者存在负权环。
具体步骤如下：1.创建一个距离数组dist[]，用于记录每个节点到源节点的当前最短路径长度。
初始化dist[]为无穷大，源节点的距离为0。
2.重复以下步骤n-1次（其中n是图中节点的个数）：-对于图中的每条边(u, v)，如果dist[u] + weight(u, v)比dist[v]更小，则更新dist[v]。
单源最短路算法范文
单源最短路算法范文1. Dijkstra算法Dijkstra算法，是由荷兰计算机科学家Edsger W. Dijkstra于1956年提出的一种解决单源最短路径问题的算法。
该算法运用了贪心思想，即每次选择当前最短路径的顶点作为中间点，不断更新各个顶点的最短路径长度。
算法步骤如下：1）将起点到所有其他顶点的最短路径长度初始化为无穷大，将起点到自身的最短路径长度设为0。
2）选取起点作为当前顶点。
3）更新当前顶点到所有相邻顶点的最短路径长度。
若当前顶点到一些相邻顶点的路径长度更短，则更新该最短路径长度。
4）选择当前最短路径长度中最小的顶点，并将其作为新的当前顶点。
5）重复步骤3和步骤4，直到所有顶点的最短路径长度被确定。
Dijkstra算法的时间复杂度为O(V^2)，其中V是顶点数。
该算法相对简单，适用于有向无环图以及所有边的权重非负的情况。
2. Bellman-Ford算法Bellman-Ford算法，是由美国计算机科学家Richard Bellman和杰出的计算机科学家Leslie Ford于1958年提出的一种解决单源最短路径问题的算法。
该算法运用了动态规划的思想，通过对所有边进行，V，-1轮松弛操作来逐步逼近最短路径。
算法步骤如下：1）将起点到所有其他顶点的最短路径长度初始化为无穷大，将起点到自身的最短路径长度设为0。
2）重复进行，V，-1轮松弛操作，其中，V，是顶点数。
3）在每一轮松弛操作中，遍历所有边，对每条边(u,v)进行松弛操作：若当前顶点u到起点的最短路径长度加上(u,v)的权重小于顶点v的最短路径长度，则更新顶点v的最短路径长度。
4）最后，检查图中是否存在负环路。
若在，V，-1轮松弛操作之后，仍然有顶点的最短路径长度能够被更新，则说明图中存在负环路。
Bellman-Ford算法的时间复杂度为O(VE)，其中V是顶点数，E是边数。
相较于Dijkstra算法，Bellman-Ford算法可以处理存在负边权以及存在负环路的情况。
单源最短路径算法
单源最短路径算法常见的单源最短路径算法有迪杰斯特拉算法(Dijkstra's algorithm)和贝尔曼-福特算法(Bellman-Ford algorithm)。
本文将详细介绍这两种算法的实现原理和特点。
1.迪杰斯特拉算法：迪杰斯特拉算法是一种用于求解带权重图的单源最短路径的算法。
它的基本思想是，维护一个集合S，初始时包含源节点，不断地向集合S中加入离源节点最近的节点，直到所有节点都加入了集合S。
在每次加入节点的过程中，更新源节点到集合S中每个节点的最短距离。
迪杰斯特拉算法的步骤如下：1)初始化源节点的最短距离为0，其他节点的最短距离为无穷大。
2)将源节点加入集合S。
3)对于源节点的每个邻居节点，更新从源节点到邻居节点的最短距离。
如果更新后的距离更短，更新邻居节点的最短距离。
4)从集合S中选择一个离源节点最近的节点加入集合S，并重复步骤35)重复步骤4，直到所有节点都加入了集合S。
迪杰斯特拉算法的时间复杂度为O(V^2)，其中V是节点的数量。
在稠密图中，即边的数量接近节点的数量平方时，迪杰斯特拉算法表现较好。
2.贝尔曼-福特算法：贝尔曼-福特算法是一种用于求解带有负权重边的单源最短路径的算法。
与迪杰斯特拉算法不同的是，贝尔曼-福特算法可以处理负权重边。
贝尔曼-福特算法的基本思想是，通过对边进行松弛操作，不断地更新节点的最短距离，直到找到所有节点的最短距离。
算法的步骤如下：1)初始化源节点的最短距离为0，其他节点的最短距离为无穷大。
2)对于边的数量-1次迭代，做以下操作：a)遍历所有边，对每条边(u,v)，如果源节点u的最短距离加上边的权重w小于目标节点v的最短距离，则更新目标节点v的最短距离。
3)再进行一次遍历，如果仍然存在可以松弛的边，则说明存在负权重环。
贝尔曼-福特算法的时间复杂度为O(V*E)，其中V是节点的数量，E 是边的数量。
相较于迪杰斯特拉算法，贝尔曼-福特算法的时间复杂度更高，但是它可以处理带有负权重边的图。
求解单源最短路径问题的算法
求解单源最短路径问题的算法单源最短路径问题是指从图中的一个顶点到其他所有顶点的最短路径的问题。
下面将详细介绍两种经典的求解该问题的算法：Dijkstra算法和Bellman-Ford 算法。
1. Dijkstra算法：- 初始化：将源顶点的距离初始化为0，其他顶点的距离初始化为无穷大。
创建一个集合S，记录已经确定最短路径的顶点。
- 重复以下步骤，直到集合S包含所有顶点：- 从未确定最短路径的顶点中选择距离源顶点最近的顶点u，并将其加入集合S。
- 对于与u相邻的顶点v，更新其距离为：min(distance[v], distance[u] + weight(u, v))，其中weight(u, v)表示边(u, v)的权值。
- 最终得到源顶点到图中所有其他顶点的最短路径。
2. Bellman-Ford算法：- 初始化：将源顶点的距离初始化为0，其他顶点的距离初始化为无穷大。
- 重复以下步骤，执行V-1次（V为顶点数）：- 遍历图中的所有边，对于每条边(u, v)，更新顶点v的距离为：min(distance[v], distance[u] + weight(u, v))。
- 检查是否存在负权回路：再次遍历所有边，如果对于边(u, v)，发现distance[v] > distance[u] + weight(u, v)，则说明存在从源顶点可达的负权回路，无法确定最短路径；否则，最短路径已经确定。
Dijkstra算法适用于无负权边且图稠密的情况，时间复杂度为O(V^2)，也可以通过最小堆优化（时间复杂度为O((V+E)logV)）。
Bellman-Ford算法适用于有负权边或存在负权回路的情况，时间复杂度为O(VE)。
需要注意的是，以上算法都是解决单源最短路径问题的经典算法，也可以使用其他如SPFA、Floyd-Warshall等算法求解，选择合适的算法应根据具体问题的要求和图的特性进行评估和选择。
求解单源最短路径问题的算法
求解单源最短路径问题的算法（实用版）目录1.单源最短路径问题的定义2.算法的基本思想3.Dijkstra 算法的实现4.算法的适用范围和优缺点正文一、单源最短路径问题的定义单源最短路径问题是指在有向图或无向图中，从某一指定顶点（源顶点）到其他所有顶点的最短路径问题。
换句话说，就是要找到从源顶点到其他所有顶点的最短路径。
这个问题在计算机科学和网络科学中有着广泛的应用，例如在社交网络分析、路由算法等方面。
二、算法的基本思想求解单源最短路径问题的算法有很多种，但其中最著名且最有效的是Dijkstra 算法。
Dijkstra 算法的基本思想是每次找到当前未被访问过的顶点中距离源顶点最近的顶点，然后更新其他顶点到源顶点的距离。
重复这个过程，直到所有顶点都被访问过为止。
三、Dijkstra 算法的实现Dijkstra 算法的具体实现如下：1.创建一个集合 S，用于存储已访问过的顶点，初始时只包含源顶点。
2.对于每个顶点，计算其到源顶点的距离，并将这个距离与其它已知距离进行比较。
3.如果这个距离比已知的距离更短，那么就更新其他顶点到源顶点的距离，并将这个顶点加入集合 S。
4.重复步骤 2 和 3，直到所有顶点都被访问过。
四、算法的适用范围和优缺点Dijkstra 算法适用于有向图和无向图，并且可以处理负权边。
但是，它有一个明显的缺点，那就是在处理大规模数据时，需要大量的内存来存储中间结果。
此外，Dijkstra 算法的时间复杂度为 O(E*logV)，其中 E 为边数，V 为顶点数。
虽然这个时间复杂度在很多情况下是可以接受的，但是在大规模数据下，可能会需要较长的时间来计算。
单源点最短路径问题常用算法
单源点最短路径问题常用算法单源点最短路径问题是图论中的经典问题，其目标是在给定图中找到从源点到其他所有顶点的最短路径。
常用的解决该问题的算法包括迪杰斯特拉算法、贝尔曼-福特算法、弗洛伊德-沃沙尔算法、A*搜索算法和SPFA算法。
本文将依次介绍这些算法的原理和实现方法，并分析它们的优缺点。
1. 迪杰斯特拉算法（Dijkstra's Algorithm）迪杰斯特拉算法是一种贪心算法，它从源点开始逐步扩展到其他顶点，每次选择当前距离源点最近的顶点进行扩展，直到遍历完所有顶点。
该算法的时间复杂度为O(n^2)，其中n为顶点数。
实现方法：(1) 初始化：将源点距离设为0，其他顶点距离设为正无穷大。
(2) 选择一个距离源点最近的顶点，将其加入已访问集合。
(3) 对于该顶点的所有邻居，更新它们到源点的距离（如果新的距离比原来的距离小）。
(4) 重复步骤2和3，直到所有顶点都被访问过。
优缺点分析：优点：算法简单直观，适用于稀疏图。
缺点：不适合处理带有负权边的图，因为可能会选到负权环中的顶点。
2. 贝尔曼-福特算法（Bellman-Ford Algorithm）贝尔曼-福特算法也是一种贪心算法，但它可以处理带有负权边的图。
该算法从源点开始遍历图的所有边，更新每条边的权值，并检查是否存在负权环。
如果存在负权环，则该边的权值将无限循环，因此需要停止遍历并报告错误。
该算法的时间复杂度为O(nm)，其中n 为顶点数，m为边数。
实现方法：(1) 初始化：将源点距离设为0，其他顶点距离设为正无穷大。
(2) 从源点开始遍历图的所有边，更新每条边的权值。
(3) 对于每个顶点，检查是否存在负权环。
如果存在，则停止遍历并报告错误。
优缺点分析：优点：可以处理带有负权边的图，并且可以检测是否存在负权环。
缺点：时间复杂度较高，且无法优化处理稀疏图。
同时，如果图中存在负权环，算法将无法给出正确的最短路径。
3. 弗洛伊德-沃沙尔算法（Floyd-Warshall Algorithm）弗洛伊德-沃沙尔算法是一种动态规划算法，它通过逐步构建中间顶点的最短路径来找到源点到所有其他顶点的最短路径。
单源最短路径算法
单源最短路径算法单源最短路径算法：1. 介绍：单源最短路径算法是指从一个特定的节点出发，通过最短路径算法求出在一个有向图中从该节点到所有其他节点的最短路径。
它把有向图要解决的问题划分为多个子问题来解决，各个子问题在组合解决方案时，子问题体现出来的更小的子问题有其更小的解，有的解可能是最优的。
单源最短路径算法既可以解决简单的有向图问题，也可以解决更复杂的有向图问题，如多边权图、有向网络等。
2. 定义与基本概念：单源最短路径算法中常见的一些基本概念包括：图(Graph)、边(Edge)、节点(Vertex)、权重(Weight)。
图是一种数据结构，它由若干节点和关联的边组成，是可以表达复杂数据关系的抽象数据类型；边是表示从一个节点指向另一个节点的连接；节点是图的基本单位，表示在图的一个位置；权重是一个网络中每条边所具有的值得，表示两个节点之间的距离或者需要消耗的时间。
3. 核心思想单源最短路径算法的核心思想是通过不断寻找与每个节点有已知最短路径的前驱节点，来求出一条最优路径。
该算法以最初的节点作为起点，为每个节点设定两个值：起点到该节点的最短路径长度，以及最短路径上的前驱节点。
根据该节点的前驱节点的信息，再到前驱节点求解最短路径，从而得到从起点到该节点的最短路径，从而解决最短路径问题。
4. 常见的单源最短路径算法一般的单源最短路径算法有：深度优先搜索法、广度优先搜索法、dijkstra算法和Bellman-Ford算法等。
深度优先搜索法是从搜索起点出发，沿着树的深度遍历树的节点，直到找到满足条件的叶子节点，再回到上一层，回溯，继续前进，直到遍历完整棵树为止。
广度优先搜索法是按照深度从上到下遍历，当搜索某一层节点，再搜索它们的所有子节点，直到找到满足条件的节点，然后再逐步回溯，直到遍历完整棵树。
Dijkstra算法又被称为单源最短路径算法，它的核心思想是求出从源点到任何一个节点的最短路径，该算法采用贪心策略，不断地更新未求出的点的最短路径，最终能够求出从源点到其他的所有点的最短路径。
单源最短路问题
单源最短路问题（SSSP问题）单源最短路问题指的是该顶点至所有可达顶点的最短路径问题.约定：从start到点i的距离为d[i]。
如果d[i]==INF，说明start和i不连通。
(1) Dijkstra算法! [邻接矩阵]Dijkstra算法是贪心算法。
它只适用于所有边的权都大于0的图。
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
基本思想通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算).此外，引进两个集合S和U。
S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
操作步骤(1)初始时，S只包含起点s；U包含除s外的其他顶点,且U中顶点的距离为"起点s到该顶点的距离"[如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。
(2)从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。
(3)更新U中各个顶点到起点s的距离。
之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。
(4)重复步骤(2)和(3)，直到遍历完所有顶点。
代码：时间复杂度：O(n2)bool visited[N]; // 是否被标号int d[N]; // 从起点到某点的最短路径长度int prev[N]; // 通过追踪prev可以得到具体的最短路径（注意这里是逆序的）void Dijkstra(int start){// 初始化：d[start]=0，且所有点都未被标号memset(visited, 0, sizeof(visited));for (int i=0; i<n; i++) d[i]=INF;d[start]=0;// 计算n次for (int i=0; i<n; i++){int x, min=INF;// 在所有未标号的结点中，选择一个d值最小的点x。
单源最短路算法及其应用
过松弛操作了，所以d[u]的值不会再发生改变。因此d[u]= (s,u)。
（证毕）
效率:
用一维数组来实现优先队列Q，O( V 2)，适用于中等规模的稠密
图
二叉堆来实现优先队列Q，O((E+V)logV)，适用于稀疏图
用Fibonacci堆来实现优先队列Q的话，O(VlogV)，可惜编程复杂 度过高，理论价值远大于实用价值
松弛技术
对每个结点v V，我们设置一属性d[v]来 描述从源s到v的最短路径的权的上界，称之为 最短路径估计。我们通过下面的过程对最短路 径估计和先辈初始化。
INITIALIZE-SINGLE-SOURCE(G,s)
1. For 每个结点 v V[G]
2. Do d[v] ←
3.
[v] ← NIL
从结点u到结点v的最短路径定义为权 w( p) v) 的任何路径。
在乘车旅行的例子中，我们可以把公路地 图模型化为一个图：结点表示路口，边表示连 接两个路口的公路，边权表示公路的长度。我 们的目标是从起点出发找一条到达目的地的最 短路径。
边的权常被解释为一种度量方法，而不 仅仅是距离。它们常常被用来表示时间、金 钱、罚款、损失或任何其他沿路径线性积累 的数量形式。
4. d[s] 0
一次松弛操作可以减小最短路径的估计值 d[v]并更新v的先辈域[v]
RELAX(u,v,w)
1. If d[v] > d[u] + w(u,v)
2. Then d[v] ← d[u] + w(u,v)
3.
[v] ← u
单源最短路
每个算法都调用INITIALIZE-SIGNLE-SOURCE，然后 利用对边进行松弛的过程。另外还要说明的是松弛是改变最 短路径估计和先辈的唯一方式。各种算法之间的相互区别在 于对每条边进行松弛操作的次数以及对边执行松弛操作的次 序有所不同。在Dijkstra算法以及关于有向无回路的最短路 径算法中，对每条边执行松弛操作一次。在Bellman-ford算 法中，对每条边要执行多次松弛操作。
（证毕）
效率:
用一维数组来实现优先队列Q，O( V 2)，适用于中等规模的稠密
图
二叉堆来实现优先队列Q，O((E+V)logV)，适用于稀疏图
用Fibonacci堆来实现优先队列Q的话，O(VlogV)，可惜编程复杂 度过高，理论价值远大于实用价值
松弛技术
对每个结点v V，我们设置一属性d[v]来 描述从源s到v的最短路径的权的上界，称之为 最短路径估计。我们通过下面的过程对最短路 径估计和先辈初始化。
INITIALIZE-SINGLE-SOURCE(G,s)
1. For 每个结点 v V[G]
2. Do d[v] ←
3.
[v] ← NIL
从结点u到结点v的最短路径定义为权 w( p) v) 的任何路径。
在乘车旅行的例子中，我们可以把公路地 图模型化为一个图：结点表示路口，边表示连 接两个路口的公路，边权表示公路的长度。我 们的目标是从起点出发找一条到达目的地的最 短路径。
边的权常被解释为一种度量方法，而不 仅仅是距离。它们常常被用来表示时间、金 钱、罚款、损失或任何其他沿路径线性积累 的数量形式。
4. d[s] 0
一次松弛操作可以减小最短路径的估计值 d[v]并更新v的先辈域[v]
RELAX(u,v,w)
1. If d[v] > d[u] + w(u,v)
2. Then d[v] ← d[u] + w(u,v)
3.
[v] ← u
单源最短路
每个算法都调用INITIALIZE-SIGNLE-SOURCE，然后 利用对边进行松弛的过程。另外还要说明的是松弛是改变最 短路径估计和先辈的唯一方式。各种算法之间的相互区别在 于对每条边进行松弛操作的次数以及对边执行松弛操作的次 序有所不同。在Dijkstra算法以及关于有向无回路的最短路 径算法中，对每条边执行松弛操作一次。在Bellman-ford算 法中，对每条边要执行多次松弛操作。
单源最短路径算法
单源最短路径算法这篇文章将介绍两种常用的单源最短路径算法，Dijkstra算法和Bellman-Ford算法，它们分别使用了贪心法和动态规划的思想来解决该问题。
一、Dijkstra算法：Dijkstra算法是一种贪心法的算法，以其发明者荷兰计算机科学家Edsger W. Dijkstra的名字命名。
它的基本思想是通过逐步扩展已知最短路径集合，直到找到从起始节点到目标节点的最短路径为止。
算法步骤如下：1.初始化距离数组，将起始节点到所有其他节点的距离初始化为无限大。
2.将起始节点的距离设置为0。
3.对于与起始节点直接相连的节点，更新距离数组的值为起始节点到这些节点的距离。
4.选择距离数组中值最小且未访问过的节点作为下一个当前节点。
5.更新从起始节点到当前节点经过未访问过的节点的距离，并更新距离数组中的值。
6.重复步骤4和5，直到所有节点都被访问过或者无法再找到更短的路径。
Dijkstra算法的时间复杂度为O(V^2)，其中V为图中节点的数量。
使用优先队列或堆数据结构可以将时间复杂度降低到O((V+E)logV)。
二、Bellman-Ford算法：Bellman-Ford算法是一种动态规划的算法，它以其发明者Richard Bellman和Leslie Ford的名字命名。
与Dijkstra算法不同的是，Bellman-Ford算法可以处理含有负权边的图。
算法步骤如下：1.初始化距离数组，将起始节点到所有其他节点的距离初始化为无限大。
2.将起始节点的距离设置为0。
3.对于每条边，更新距离数组的值为起始节点到目标节点的距离。
4.重复步骤3，直到所有节点的距离不再改变。
5.检查是否存在负权回路，如果存在，说明不存在最短路径。
Bellman-Ford算法的时间复杂度为O(VE)，其中V为图中节点的数量，E为图中边的数量。
总结：Dijkstra算法和Bellman-Ford算法是解决单源最短路径问题的两种常用算法。
算法合集之《最短路算法及其应用》
地的最快路线。
总结词
路径规划是利用最短路 算法找到从起点到终点 的最短路径或最优路径
的过程。
详细描述
在交通、物流、通信和 计算机科学等领域，路 径规划应用广泛。例如 ，在地图导航中，最短 路径算法可以帮助用户 找到从当前位置到目的
地的最快路线。
物流配送
总结词
物流配送中，最短路算法用于优化配 送路线，降低运输成本和提高效率。
地图导航
总结词
地图导航是利用最短路算法为用户提供从起点到目的地的最佳路线建 议。
详细描述
地图导航系统通过最短路径算法计算出行驶时间最短、距离最短的路 线，并实时更新路况信息，为用户提供最优的出行建议。
总结词
地图导航是利用最短路算法为用户提供从起点到目的地的最佳路线建 议。
详细描述
地图导航系统通过最短路径算法计算出行驶时间最短、距离最短的路 线，并实时更新路况信息，为用户提供最优的出行建议。
适用于解决单源最短路径问题，如路 由、导航、物流配送等。
Bellman-Ford算法
01 总结词
Bellman-Ford算法是一种适用 于带负权重边的单源最短路径 算法。
02
详细描述
Bellman-Ford算法的基本思想 是利用动态规划的思想，从源 节点开始，逐步更新每个节点 到源节点的最短距离。该算法 可以处理带负权重的边，但在 最坏情况下可能会需要多次遍 历所有边。
感谢观看
，降低运输成本和提高派送效率。
案例三
总结词
全局优化、实时性强
详细描述
Floyd-Warshall算法是一种用于计算所有节点对之间 最短路径的动态规划算法。在网络流量控制中，该算 法能够实时监测网络流量状况，并根据流量的变化动 态调整路由，实现网络流量的全局优化，提高网络性 能和稳定性。
总结词
路径规划是利用最短路 算法找到从起点到终点 的最短路径或最优路径
的过程。
详细描述
在交通、物流、通信和 计算机科学等领域，路 径规划应用广泛。例如 ，在地图导航中，最短 路径算法可以帮助用户 找到从当前位置到目的
地的最快路线。
物流配送
总结词
物流配送中，最短路算法用于优化配 送路线，降低运输成本和提高效率。
地图导航
总结词
地图导航是利用最短路算法为用户提供从起点到目的地的最佳路线建 议。
详细描述
地图导航系统通过最短路径算法计算出行驶时间最短、距离最短的路 线，并实时更新路况信息，为用户提供最优的出行建议。
总结词
地图导航是利用最短路算法为用户提供从起点到目的地的最佳路线建 议。
详细描述
地图导航系统通过最短路径算法计算出行驶时间最短、距离最短的路 线，并实时更新路况信息，为用户提供最优的出行建议。
适用于解决单源最短路径问题，如路 由、导航、物流配送等。
Bellman-Ford算法
01 总结词
Bellman-Ford算法是一种适用 于带负权重边的单源最短路径 算法。
02
详细描述
Bellman-Ford算法的基本思想 是利用动态规划的思想，从源 节点开始，逐步更新每个节点 到源节点的最短距离。该算法 可以处理带负权重的边，但在 最坏情况下可能会需要多次遍 历所有边。
感谢观看
，降低运输成本和提高派送效率。
案例三
总结词
全局优化、实时性强
详细描述
Floyd-Warshall算法是一种用于计算所有节点对之间 最短路径的动态规划算法。在网络流量控制中，该算 法能够实时监测网络流量状况，并根据流量的变化动 态调整路由，实现网络流量的全局优化，提高网络性 能和稳定性。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
Dijkstra(G,w,s) 1. INITIALIZE-SINGLE-SOURCE(G,S) 2. S 3. Q ← V[G] 4. While Q 5. Do u ← EXTRACT-MIN(Q) 6. S ← S U {u} 7. For 每个顶点v Adj[u] 8. Do RELAX(u,v,w)
一种可能的方法是枚举出所有路径，并计算 出每条路径的长度，然后选择最短的一条。 然而我们很容易看到，即使不考虑含回路 的路径，依然存在数以百万计的行车路线! 实际上，其中绝大多数路线我们是没必 要考虑的。 这时候，我们应该用一种系统的方法来 解决问题，而不是通常人们所用的凑的方法 和凭经验的方法。
SPFA算法
适用条件: 任意边权为实数的图
定理3 只要最短路径存在，上述SPFA算法必定能求出最小值。 证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的 优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d 越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短 路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到 达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最 短路径值。（证毕） 定理4 在平均情况下，SPFA算法的期望时间复杂度为O(E)。 证明：上述算法每次取出队首结点u，并访问u的所有临结点的复杂度 为O(d)，其中d为点u的出度。运用均摊分析的思想，对于|V|个点|E|条 E E 边的图，点的平均出度为 V，所以每处理一个点的复杂度为O(V )。假 设结点入队次数为h，显然h随图的不同而不同。但它仅与边权值分布 E h T O h O E O(kE ) 有关。我们设h=kV，则算法SPFA的时间复杂度为 V V 在平均的情况下，可以将k看成一个比较小的常数，所以SPFA算法在 一般情况下的时间复杂度为O(E)。（证毕）
Dijkstra算法
适用条件: 所有边的权值非负 定理2 每当结点u插入集合S时，有d[u]= (s,u)成立。 简证：我们每次选择在集合V-S中具有最小最短路径估计的结点u， 因为我们约定所有的边权值非负，所以有可能对结点u进行松弛操 作的结点必不在集合V-S中（否则与结点u的定义矛盾），因此只会 在集合S中。又由于我们选取结点进入S时，S中的结点已全部进行 过松弛操作了，所以d[u]的值不会再发生改变。因此d[u]= (s,u)。 （证毕） 效率: 用一维数组来实现优先队列Q，O( V 2)，适用于中等规模的稠密 图 二叉堆来实现优先队列Q，O((E+V)logV)，适用于稀疏图 用Fibonacci堆来实现优先队列Q的话，O(VlogV)，可惜编程复杂 度过高，理论价值远大于实用价值
一次松弛操作可以减小最短路径的估计值 d[v]并更新v的先辈域[v]
RELAX(u,v,w) 1. If d[v] > d[u] + w(u,v) 2. Then d[v] ← d[u] + w(u,v) ←u 3. [v]
单源最短路
每个算法都调用INITIALIZE-SIGNLE-SOURCE，然后 利用对边进行松弛的过程。另外还要说明的是松弛是改变最 短路径估计和先辈的唯一方式。各种算法之间的相互区别在 于对每条边进行松弛操作的次数以及对边执行松弛操作的次 序有所不同。在Dijkstra算法以及关于有向无回路的最短路 径算法中，对每条边执行松弛操作一次。在Bellman-ford算 法中，对每条边要执行多次松弛操作。
松弛技术
对每个结点v V，我们设置一属性d[v]来 描述从源s到v的最短路径的权的上界，称之为 最短路径估计。我们通过下面的过程对最短路 径估计和先辈初始化。
INITIALIZE-SINGLE-SOURCE(G,s) 1. For 每个结点 v V[G] 2. Do d[v] ← [v] ← NIL 3. 4. d[s] 0
Bellman-Ford算法
适用条件: 任意边权为实数的图 Bellman-Ford算法的思想基于以下事实：“两点间如果有最短路，那 么每个结点最多经过一次。也就是说，这条路不超过n-1条边。”（如 果一个结点经过了两次，那么我们走了一个圈。如果这个圈的权为正， 显然不划算；如果是负圈，那么最短路不存在；如果是零圈，去掉不 影响最优值） 根据最短路的最优子结构（定理1），路径边数上限为k时的最短路可以 由边数上限为k-1时的最短路“加一条边”来求，而根据刚才的结论，最 多只需要迭代n-1次就可以求出最短路。 效率: Bellman-Ford算法的运行时间为O(VE)。很多时候，我们的算法并不 需要运行|V|-1次就能得到最优值。对于一次完整的第3-4行操作，要是 一个结点的最短路径估计值也没能更新，就可以退出了。 经过优化后，对于多数情况而言，程序的实际运行效率将远离O(VE)而 变为O(kE)，其中k是一个比|V|小很多的数。
从结点u到结点v的最短路径定义为权 w( p) v) 的任何路径。
在乘车旅行的例子中，我们可以把公路地 图模型化为一个图：结点表示路口，边表示连 接两个路口的公路，边权表示公路的长度。我 们的目标是从起点出发找一条到达目的地的最 短路径。 边的权常被解释为一种度量方法，而不 仅仅是距离。它们常常被用来表示时间、金 钱、罚款、损失或任何其他沿路径线性积累 的数量形式。
重要性质
定理1 (最优子结构) 给定有向加权图G=(V,E)，设 P=<v1, v2,…, vk>为从结点v1到结点vk的一条最短路 径，对任意i,j有i<=j<=k，设Pij=< vi, vi+1,…, vj>为从vi 到vj的P的子路径,则Pij是从vi到vj的一条最短路径。 证明：我们把路径P分解为 <v1,v2,…,vi,vi+1,…vj,…vk>。则 w(P)=w(P1i)+w(Pij)+w(Pjk)。现在假设从vi到vj存在一 路径P’ij，且w(P’ij)<w(Pij)，则将P中的路径 Pij=(vi,vi+1,…vj)替换成P’ij，依然是从v1到vk的一条路 径，且其权值 w(P1i)+w(P’ij)+w(Pjk)小于w(P)，这与前 提P是从v1到vk的最短路径矛盾。（证毕）
定义
在最短路问题中，给出的是一有向加权图 G=(V,E)，在其上定义的加权函数W:E→R为从 边到实型权值的映射。路径P=(v0, v1,……, vk) 的权是指其组成边的所有权值之和：
w( p )
w(v
i 1
k
i 1
, vi )
定义u到v间最短路径的权为：
v)
minw( p ):u v 如果存在由u到v的通路 如果不存在
例一 双调路径 (BOI2002)
题意简述：
如今的道路密度越来越大，收费也越来越多，因此选择最佳路径是很现实的 问题。城市的道路是双向的，每条道路有固定的旅行时间以及需要支付的费 用。路径由连续的道路组成。总时间是各条道路旅行时间的和，总费用是各 条道路所支付费用的总和。同样的出发地和目的地，如果路径A比路径B所需 时间少且费用低，那么我们说路径A比路径B好。对于某条路径，如果没有其 他路径比它好，那么该路径被称为最优双调路径。这样的路径可能不止一条， 或者说根本不存在。 给出城市交通网的描述信息，起始点和终点城市，求最优双条路径的条数。 城市不超过100个，边数不超过300，每条边上的费用和时间都不超过100。
小结
Dijkstra算法的效率高，但是也有局限性，就是对于含负权的图 无能为力。 Bellman-Ford算法对于所有最短路长存在的图都适用，但是效率常 常不尽人意。 SPFA算法可以说是综合了上述两者的优点。它的效率同样很不错， 而且对于最短路长存在的图都适用，无论是否存在负权。它的编程 复杂度也很低，是高性价比的算法。 算法 Dijkstra 时间复杂度 O( V )或 O((E+V)logV)
最短路算法及其应用
广东北江中学 余远铭 yyming@
最短路问题是图论中的核心问题之一， 它是许多更深层算法的基础。同时，该问题 有着大量的生产实际的背景。不少问题从表 面上看与最短路问题没有什么关系，却也可 以归结为最短路问题。 一个在生活中常见的例子是:
乘汽车旅行的人总希望找出到目的地尽 可能短的行程。如果有一张地图并在地图上 标出了每对十字路口之间的距离，如何找出 这一最短行程？
Bellman-Ford算法
Bellman-Ford算法运用了松弛技术，对每一结点v V，逐步 减小从源s到v的最短路径的估计值d[v]直至其达到实际最短路径的 权 (s,v)，如果图中存在负权回路，算法将会报告最短路不存在。 Bellman-Ford(G,w,s) 1. INITIALIZE-SINGLE-SOURCE(G,s) 2. For i ← 1 to |V[G]|-1 3. Do For 每条边(u,v) E[G] 4. Do RELAX(u,v,w) 5. For 每条边(u,v) E[G] 6. Do If d[v] > d[u] + w(u, v) 7. Then Return FALSE 8. Return TRUE
2
空间复杂度 O(V )或 O(E+V)
2
编程复杂度 简单或 相对复杂
适用范围 不含负权的 图(窄)
Bellman-Ford
SPFA
O(VE)
O(E)
O(E+)
O(E+V)
简单
简单
实数图(广)
实数图(广)
我们应该根据实际需要，找到时空复杂度和编程复杂度的平衡点，在 考场上用最少的时间拿尽可能多的分数。
常用算法
一、Dijkstra算法
二、Bellman-Ford算法
三、SPFA算法