最短路径
- 格式：doc
- 大小：128.50 KB
- 文档页数：8
文档推荐
-
基于Dijkstra算法最短路径设计页数:5
-
基于arcgis最短路径分析页数:88
-
基于GIS的城市道路网最短路径分析页数:8
-
实验报告：基于最短路径分析与应用页数:6
-
最短路径算法及应用页数:16
-
最短路径算法附应用页数:16
下载文档原格式
合集下载
最短路径和简单路径的关系
最短路径和简单路径的关系在这个信息爆炸的时代，最短路径和简单路径的概念可谓是我们的生活中不可或缺的部分。
说到最短路径，咱们首先得明白，最短路径就是在一个网络中，连接两个点的最直接、最有效的路线，听上去是不是很简单？想象一下，你要从家到公司，当然希望选一条不堵车的捷径，让你早早到达，喝上一杯咖啡，打个瞌睡，那才叫生活的乐趣呢！而简单路径呢，就是在连接这些点的过程中，尽量不走重复的路线，简单来说，就是不走回头路，不浪费时间。
1. 最短路径的魅力1.1 直奔主题最短路径的好处，大家都是心知肚明的。
就像一条顺畅的高速公路，直通目标，不费周章。
而且，找到这条最短路径，不仅能节省时间，还能节省资源。
想想，开车的时候，油耗可不是个小数目，走错了路，油表可就直线下降，心疼得很！而在生活中，找到最短路径，也能让你在复杂的选择中，理智而高效。
1.2 实际应用在现实生活中，最短路径的概念可广泛应用于很多场景。
比如，快递小哥为了在最短时间内送到你的包裹，会不断计算路线；又比如，GPS导航系统通过不断分析路况，为你推荐最佳路线。
这一切的一切，都是在追求那条最短的、最迅速的路径，让生活更加顺畅。
不过，这个“最短”可不是说一味地走近路，有时候，走一条小路可能会让你发现意想不到的风景。
2. 简单路径的意义2.1 避免重复简单路径的意义在于避免走冤屈路，就像生活中，很多时候我们需要做出选择，而这些选择可能会重叠，造成时间和精力的浪费。
走一条简单路径，能让我们更加专注于目标，心无旁骛。
比如，去商场买东西，如果你总是从同一个地方进出，不但浪费时间，还可能错过那些打折商品，岂不是得不偿失？2.2 生活中的应用在日常生活中，我们可以看到简单路径的身影。
比如，朋友聚会，总有些人喜欢绕圈圈，结果大家都等得不耐烦了；而有的人就会直接了当，提出一个简单明了的计划，大家一拍即合，分分钟搞定。
这种情况下，简单路径不仅提升了效率，还让大家的心情都好得多，像是阳光普照，心里暖暖的。
最短路径问题介绍
最短路径问题介绍全文共四篇示例，供读者参考第一篇示例：最短路径问题是指在一个带有边权的图中，寻找连接图中两个特定节点的最短路径的问题。
在实际生活中，最短路径问题广泛应用于交通运输、通信网络、物流配送等领域。
通过解决最短路径问题，可以使得资源的利用更加高效，节约时间和成本，提高运输效率，并且在紧急情况下可以迅速找到应急通道。
最短路径问题属于图论中的基础问题，通常通过图的表示方法可以简单地描述出这样一个问题。
图是由节点和边组成的集合，节点表示不同的位置或者对象，边表示节点之间的连接关系。
在最短路径问题中，每条边都有一个权重或者距离，表示从一个节点到另一个节点移动的代价。
最短路径即是在图中找到一条路径，使得该路径上的边权和最小。
在解决最短路径问题的过程中，存在着多种算法可以应用。
最著名的算法之一是Dijkstra算法，该算法由荷兰计算机科学家Edsger W. Dijkstra于1956年提出。
Dijkstra算法是一种贪心算法，用于解决单源最短路径问题，即从一个给定的起点到图中所有其他节点的最短路径。
该算法通过维护一个距离数组和一个集合来不断更新节点之间的最短距离，直到找到目标节点为止。
除了Dijkstra算法和Floyd-Warshall算法外，还有一些其他与最短路径问题相关的算法和技术。
例如A*算法是一种启发式搜索算法，结合了BFS和Dijkstra算法的特点，对图中的节点进行评估和排序，以加速搜索过程。
Bellman-Ford算法是一种解决含有负权边的最短路径问题的算法，通过多次迭代来找到最短路径。
一些基于图神经网络的深度学习方法也被应用于最短路径问题的解决中，可以获得更快速和精确的路径搜索结果。
在实际应用中，最短路径问题可以通过计算机程序来实现，利用各种算法和数据结构来求解。
利用图的邻接矩阵或者邻接表来表示图的连接关系，再结合Dijkstra或者Floyd-Warshall算法来计算最短路径。
最短路径知识点
l A 最短路径问题一、基本模型与方法问题1：“牵牛从点A 出发，到河边l 喝水，再到点B 处吃草，走哪条路径最短？”即在l 上找一点P ，使得PA+PB 和最小.（1）A ，B 两点在直线异侧时，连接AB 交l 于P ，则PA+PB 和最小.（2）A ，B 两点在直线同侧时，在l 上找一点P ，使得PA+PB 和最小.作B 点关l 的对标点B’，连接AB’交l 于点P ，即为所要找的P 点，使PA+PB 和最小.(3)变式讨论：在l 上找一P 点，使得△PAB 周长最小.问题2：在l 上找一点P ，使得|PA 一PB|最大（1）A ，B 两点在直线同侧时，连接AB 井延长交l 于P ，则|PA 一PB|最大（2）A ，B 两点在直线异侧时，作B 点关于l 的对称点B’，连接AB’并延长交l 于点P ，即为所要找的P 点，使|PA 一PB|最大.（3）当两定点A 、B 在直线l 同侧时，在直线l 上找一点P ，使得PA PB 最小． l A l A l l A问题3：（1）在直线l 1、l 2上分别求点M 、N ，使△PMN 周长最小做法：分别作点P 关于直线l 1、l 2的对称点P 1，P 2连接P 1，P 2与l 1、l 2交点即为M ，N（2）变式：在直线l 1、l 2上分别求点M 、N ，使四边形PMQN 周长最小.做法：分别作点P ，Q 关于直线l 1，l 2的对称点P’，Q’，连接P’，Q’ 与l 1，l 2交点即为M ，N问题4：点在锐角△AOB 内部，在OB 边上求作一点D ，在OA 边上求作一点C ，使PD+CD 最小做法：做点P 关于直线OB 的对称点P’，过P’向直线OA 作垂线与OB 的交点为所求点D ，垂足即为点C问题5：（1）直线l 1△l 2，并且l 1与l 2之间的距离为d ，点A 和点B 分别在直线l 1、l 2的两 侧，在直线l 1、l 2上分别求一点M 、N ，使AM+MN+AB 的和最小.作法：将点A 向下平移d 个单位到A 1，连结A 1B 交l 2于点N ，过N 作MN△”1，垂足为M ，连结AM ，则线段AM+MN+NB 的和最小，点M ，N 即为所求. l ABl 22O（2）直线l 的同侧有两点A ，B ，在直线l 上求两点C 、D ，使得AC+CD+DB 的和最小，且CD 的长为定值a ，点D 在点C 的右侧.作法：将点A 向右平移a 个单位到A 1，作点B 关于直线的对称点名B 1，连结A 1，B 1交直线l 于点D ，过点A 作AC//A 1D 交直线l 于点G ，连结BD ，则线段AC+CD+DB 的和最小. 点C 、D 即为所求二、基本题型训练(欢迎大家补充练习题并上传！)1. 如图，已知△ABC 为等腰直角三角形，AC ＝BC ＝4，∠BCD ＝15°，P 为CD 上的动点，则PA PB的最大值是多少？解答：l 21如图所示，作点A关于CD的对称点A′，连接A′C，连接A′B并延长交CD于点P，则点P就是PA PB-的值最大时的点，PA PB-＝A′B．∵△ABC为等腰直角三角形，AC＝BC等于4，∴∠ACB＝90°．∵∠BCD＝15°，∴∠ACD＝75°．∵点A、A′关于CD对称，∴AA′⊥CD，AC＝CA′，∵∠ACD＝∠DCA′＝75°，∴∠BCA′＝60°．∵CA′＝AC＝BC＝4，∴△A′BC是等边三角形，∴A′B＝BC＝4．∴PA PB-的最大值为4．2.。
最短路径算法
§distance[j]=distance[u]+G[u][j]; §path[j]=u; §}}}
2、算法的正确性和计算复杂性
(1)贪心选择性质 (2)最优子结构性质 (3)计算复杂性 对于具有n个顶点和e条边的带权有向图，如果用 带权邻接矩阵表示这个图，那么Dijkstra算法的主循 环体需要 O (n)时间。这个循环需要执行n-1次，所以完 O(时间。算法的其余部分所需要时间不 n2 ) 成循环需要 O(n 2 ) 超过 。
7.5所有点对的最短路径问题
§对于一个各边权值均大于0的有n个顶点的带 权有向图G=(V,E)，求所有顶点之间的最短 路径和最短距离。
图的邻接矩阵表示法
1
1 1
3
0 2
9
2
2
8 9 6
V = 2
3
L= 8 0 6
1 ∞ 0
(b )
(a )
复习Dijkstra算法
其基本思想是，设置顶点集合S并不断地作 基本思想是 设置顶点集合S 贪心选择来扩充这个集合 一个顶点属于集合S 来扩充这个集合。 贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。 当且仅当从源到该顶点的最短路径长度已知。 初始时， 中仅含有源点。 初始时，S中仅含有源点。设u是G的某一个 顶点，把从源点到u且中间只经过S 顶点，把从源点到u且中间只经过S中顶点的路称 为从源到u的特殊路径，并用数组dist distance记录 为从源到u的特殊路径，并用数组dist 记录 当前每个顶点所对应的最短特殊路径长度。 当前每个顶点所对应的最短特殊路径长度。 Dijkstra算法每次从 算法每次从V Dijkstra算法每次从V-S中取出具有最短特殊路 长度的顶点u 添加到S 长度的顶点u，将u添加到S中，同时对数组 distance作必要的修改。一旦S包含了所有V中 作必要的修改。 dist 作必要的修改 一旦S包含了所有V 顶点，distance就记录了从源到所有其它顶点 顶点，dist 就记录了从源到所有其它顶点 之间的最短路径长度。 之间的最短路径长度。
最短路径的算法
最短路径的算法最短路径的算法小河边有两个村庄A，B，要在河边建一自来水厂向A村与B村供水，若要使厂部到A，B村的距离相等，则应选择在哪建厂?要回答出这个问题，我们就要了解一下最短路径的相关知识。
以下是店铺与大家分享最短路径的知识。
最短路径最短路径，是指用于计算一个节点到所有节点的最短的线路。
主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
最短路径问题是图论研究中的一个经典算法问题，旨在图(由结点和路径组成的)中两结点之间的最短路径。
最短路径问题最短路径问题是图论研究中的一个经典算法问题，旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。
算法具体的形式包括：确定起点的最短路径问题- 即已知起始结点，求最短路径的问题。
适合使用Dijkstra算法。
确定终点的最短路径问题- 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。
在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题- 即已知起点和终点，求两结点之间的最短路径。
全局最短路径问题- 求图中所有的最短路径。
适合使用Floyd-Warshall算法。
Dijkstra算法1.定义概览Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。
主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
Dijkstra算法是很有代表性的最短路径算法，在很多课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。
注意该算法要求图中不存在负权边。
问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。
(单源最短路径)2.算法描述1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合(用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了)，第二组为其余未确定最短路径的顶点集合(用U表示)，按最短路径长度的递增次序依次把第二组的顶点加入S中。
求最短路径的算法
求最短路径的算法
最短路径算法是计算图中两个节点之间最短距离的算法。
在计算机科学中，最短路径算法是图论中最基本的算法之一。
最常见的应用是在路由算法中，用来寻找两个网络节点之间的最短路径。
最短路径算法有多种实现方式，其中最著名的算法是迪杰斯特拉算法和弗洛伊德算法。
迪杰斯特拉算法使用贪心策略，从起点开始对所有节点进行扫描，依次找到距离起点最近的节点，并更新与其相邻节点的距离。
弗洛伊德算法则是基于动态规划的思想，通过递推计算出所有节点之间的最短路径。
除了以上两种算法，还有贝尔曼-福德算法、A*算法等，它们各自适用于不同的场景。
例如，A*算法是一种启发式搜索算法，根据启发函数估计到目标节点的距离，从而更快地找到最短路径。
在实际应用中，最短路径算法被广泛使用。
例如，在地图导航中，我们需要找到最短路径来规划行程；在通信网络中，路由器需要计算出最短路径来转发数据包。
因此，掌握最短路径算法是计算机科学学习的基础，也是工程实践中必备的技能。
- 1 -。
最短路径与标号法
最短路径与标号法前面我们学习过动态规划的应用，图中没明显阶段求最短路径的问题属于无明显阶段的动态规划，通常用标号法求解，求最短路径问题是信息学奥赛中很重要的一类问题，许多问题都可转化为求图的最短路径来来解，图的最短路径在图论中有经典的算法，本章介绍求图的最短路径的dijkstra算法、Floyed算法，以及标号法。
一、最短路径的算法1、单源点最短路径（dijkstra算法）给定一个带权有向图G=（V，E），其中每条边的权是一个非负实数，另外，还给定V中的一个顶点，称为源点。
求从源点到所有其他各顶点的最短路径长度。
这个问题称为单源最短路径问题。
求单源最短路径可用dijkstra算法求解。
（dijkstra算法）算法思想：设源点为x0，dist[i]表示顶点i到源点x0的最短路径长度，map[i,j]表示图中顶点i到顶点j的长度，用数组mark对所有的顶点作标记，已求出源点到达该点J的最短路径的点J记为mark[j]=true,否则标记为false。
初始时，对源点作标记，然后从未作标记的点中找出到源点路径长度最短的顶点minj，对该顶点作标记，并对其它未作标记的点K作判断：if dist[minj]+map[minj,k]<dist[k] then dist[k]= dist[minj]+map[minj,k]。
重复处理，直到所有的顶点都已作标记，这时求出了源点到所有顶点的最短路径。
算法过程：const maxn=100;varmap: array[1..maxn,1..maxn] of integer;dist: array[1..maxn] of integer;mark: array[1..maxn] of Boolean;n,k: integer;procedure dijkstra;var I,j,min,minj,temp:integer;beginfillchar(mark,sizeof(mark),0);for I:=1 to n do dist[i]:=maxint;dist[k]:=0;for I:=1 to n-1 dobeginmin:=maxint;for j:=1 to n doif (not mark[j]) and (dist[j]<min) thenbeginmin:=dist[j]; minj:=j;end;mark[minj]:=true;for j:=1 to n doif (not mar[j]) and (map[minj,j]>0) thenbegintemp:=dist[minj]+map[minj,j];if temp<dist[j] then dist[j]:=temp;end;end;end;以上只是求出了从源点到其它所有点的最短路径长度，所经过的具体路径没有保存，如果要求出具体的路径来，那么在求最短路径的过程中要将经过的中间点记录下来。
从 v0 到各终点的最短路径及长度
在图论中，从一个节点到另一个节点所经过的路径中，有一条路径的长度最短，这个最短路径称为最短路径。
而在实际应用中，我们经常需要求解从起始点到各终点的最短路径及其长度，这是一个十分重要且基础的问题。
在本文中，我们将从简到繁，由浅入深地探讨从 v0 到各终点的最短路径及长度。
1. 单源最短路径在图论中，单源最短路径指的是求解从一个固定的起始点 v0 到图中所有其他点的最短路径及其长度。
常见的解决方法有 Dijkstra 算法和Bellman-Ford 算法。
Dijkstra 算法是一种贪心算法，它通过不断扩展已经找到的最短路径来逐步求解出所有点的最短路径。
而 Bellman-Ford 算法则是一种动态规划算法，它通过不断更新距离数组来逐步求解出所有点的最短路径。
通过这两种算法，我们可以很方便地求解出从 v0 到各终点的最短路径及长度。
2. 多源最短路径除了单源最短路径外，有时我们还需要求解图中任意两点之间的最短路径及其长度，这就是多源最短路径问题。
常见的解决方法有 Floyd-Warshall 算法和 Johnson 算法。
Floyd-Warshall 算法是一种动态规划算法，它通过不断更新距离矩阵来逐步求解出任意两点之间的最短路径。
而 Johnson 算法则是一种优化算法，它通过重新赋权和Dijkstra 算法来求解出任意两点之间的最短路径。
通过这两种算法，我们可以很方便地求解出任意两点之间的最短路径及长度。
3. 应用实例分析在实际应用中，最短路径问题有着广泛的应用。
比如在交通规划中，我们需要求解出从一个城市到另一个城市的最短路径及长度，以便合理规划交通路线。
在网络通信中，我们需要求解出从一个网络节点到另一个网络节点的最短路径及长度，以便提高数据传输效率。
在人工智能中，我们需要求解出从一个状态到另一个状态的最短路径及长度，以便优化决策过程。
通过对最短路径问题的研究和应用，我们可以更好地理解和解决实际问题。
初中最短路径问题7种类型
初中最短路径问题7种类型初中最短路径问题7种类型最短路径问题是离散数学中一个重要的研究领域，其应用广泛，包括交通路线规划、网络优化等。
对于初中学生来说，了解和掌握最短路径问题，有助于培养他们的逻辑思维和解决问题的能力。
下面将介绍初中最短路径问题的七种类型。
1. 单源最短路径问题单源最短路径问题是指在一个给定的加权有向图中，从一个确定的源点出发，求到其他所有顶点的最短路径。
这个问题可以通过使用迪杰斯特拉算法或贝尔曼-福特算法来求解。
通过学习和理解这些算法，学生可以逐步掌握寻找最短路径的基本方法。
2. 多源最短路径问题多源最短路径问题是指在一个给定的加权有向图中，求任意两个顶点之间的最短路径。
这个问题可以通过使用佛洛依德算法来解决。
学生可以通过了解和实践佛洛依德算法，掌握多源最短路径问题的求解方法。
3. 无权图最短路径问题无权图最短路径问题是指在一个无向无权图中，求从一个顶点到其他所有顶点的最短路径。
这个问题可以通过使用广度优先搜索算法来解决。
学生可以通过学习广度优先搜索算法，了解和掌握无权图最短路径问题的解决方法。
4. 具有负权边的最短路径问题具有负权边的最短路径问题是指在一个给定的加权有向图中，存在负权边，求从一个顶点到其他所有顶点的最短路径。
这个问题可以通过使用贝尔曼-福特算法来解决。
学生可以通过了解和实践贝尔曼-福特算法，理解和应用具有负权边的最短路径问题。
5. 具有负权环的最短路径问题具有负权环的最短路径问题是指在一个给定的加权有向图中，存在负权环，求从一个顶点到其他所有顶点的最短路径。
这个问题可以通过使用贝尔曼-福特算法的改进版来解决。
学生可以通过学习和理解贝尔曼-福特算法的改进版，解决具有负权环的最短路径问题。
6. 具有边权和顶点权的最短路径问题具有边权和顶点权的最短路径问题是指在一个给定的加权有向图中，除了边权之外，还考虑了顶点的权重，求从一个顶点到其他所有顶点的最短路径。
这个问题可以通过使用约翰逊算法来解决。
遍历坐标点的最短路径
遍历坐标点的最短路径介绍在计算机科学和数学中，遍历坐标点的最短路径是一个经常被研究和应用的问题。
它涉及到在给定的坐标系内找到连接两个或多个坐标点的最短路径。
最短路径可以有不同的定义，取决于具体的应用场景，例如，可以是物理路径的最短距离，或是逻辑路径上的最短步数。
在本文中，我们将深入探讨遍历坐标点的最短路径问题，并介绍几种常见的解决方法和算法。
最短路径问题的定义在遍历坐标点的最短路径问题中，我们需要找到一条路径来连接两个或多个给定的坐标点，使得该路径的长度或步数最小。
以下是最短路径问题的一般定义： - 输入：给定一个坐标系和一个或多个坐标点。
- 输出：找到连接这些坐标点的最短路径，即使路径的长度或步数最小化。
最短路径问题在计算机科学中有许多应用，如导航系统、网络路由、图像处理等。
常见的解决方法和算法在解决遍历坐标点的最短路径问题时，有几种常见的解决方法和算法可以使用。
1. 广度优先搜索算法（BFS）广度优先搜索算法是一种常用的解决最短路径问题的算法。
它从起始坐标点开始，不断扩展当前节点的邻居节点，直到找到目标节点或遍历完所有可达节点。
广度优先搜索算法的步骤如下： 1. 将起始节点放入队列中。
2. 从队列中取出节点，并将其标记为已访问。
3. 检查该节点的邻居节点，如果邻居节点未被访问过，则将其放入队列中。
4. 重复步骤2和3，直到队列为空或找到目标节点。
2. 迪杰斯特拉算法（Dijkstra’s Algorithm）迪杰斯特拉算法用于解决有权图中的最短路径问题。
它使用一种贪心的策略，在每一步选择当前节点的最短路径，并逐步扩展到其他节点。
迪杰斯特拉算法的步骤如下： 1. 初始化一个距离数组，用于存放每个节点到起始节点的最短距离。
将起始节点的距离设为0，其他节点的距离设为无穷大。
2. 选择一个未被访问的节点中距离最小的节点。
3. 更新该节点的邻居节点的最短距离，如果更新后的距离比已有的距离小，则更新距离。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
Shortest Paths最短路径译by tim greenSample Problem: Overfencing [Kolstad & Schrijvers, Spring 1999 USACO Open]农夫John在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。
幸运的是，他在迷宫的边界上留出了两段栅栏作为迷宫的出口。
更幸运的是，他所建造的迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。
给定迷宫的宽W(1<=W<=38)及长H(1<=H<=100)。
2*H+1行，每行2*W+1的字符以下面给出的格式表示一个迷宫。
然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数。
（即使从这一点以最优的方式走向最靠近的出口，它仍然需要最多的步数）当然了，牛们只会水平或垂直地在X 或Y轴上移动，他们从来不走对角线。
每移动到一个新的方格算作一步（包括移出迷宫的那一步）这是一个W=5,H=3的迷宫：+-+-+-+-+-+| |+-+ +-+ + +| | | |+ +-+-+ + +| | |+-+ +-+-+-+如上图的例子，栅栏的柱子只出现在奇数行或奇数列。
每个迷宫只有两个出口。
The Abstraction给出:一个边的权为非负的有向图∙两个顶点间的一条路径是由图中相邻的边以任意的顺序连接而成的∙两个顶点之间的最短路径是指图中连接这两个顶点的路径中代价最小的一条，一条路径的代价是指路径上所有边的权的和∙题目常常只要求出最短路径的代价而不需要求出路径本身。
在这个例子中只用求出迷宫内部的点和出口之间的最短距离(代价)。
最别的，它需在求出所有代价中最大的一个。
用Dijkstra算法来求加权图中的最短路径给出:所有的顶点、边、边的权，这个算法按离源点的距离从近到远的顺序来"访问"每个顶点。
∙开始时把所有不相邻顶点间的距离(边的权)标为无穷大,自己到自己的距离标为0。
∙每次,找出一个到源点距离最近并且没有访问过的顶点u。
现在源点到这个顶点的距离就被确定为源点到这个顶点的最短距离。
∙考虑和u相邻的每个顶点v通过u到源点的距离。
考查顶点v,看这条路径是不是更优于已知的v到源点的路径,如果是,更新v的最佳路径。
[In determining the shortest path to a particular vertex, this algorithm determines all shorter paths from the source vertex as well since no more work is required to calculate all shortest paths from a single source to vertices in a graph. ]参考: [Cormen, Leiserson, Rivest]的第25章Pseudocode:# distance(j) is distance from source vertex to vertex j# parent(j) is the vertex that precedes vertex j in any shortest path# (to reconstruct the path subsequently)1 For all nodes i2 distance(i) = infinity # not reachable yet3 visited(i) = False4 parent(i) = nil # no path to vertex yet5 distance(source) = 0 # source -> source is start of all paths6 parent(source) = nil7 8 while (nodesvisited < graphsize)9 find unvisited vertex with min distance to sourcd; call it vertex i10 assert (distance(i) != infinity, "Graph is not connected")11 visited(i) = True # mark vertex i as visited# update distances of neighbors of i12 For all neighbors j of vertex i13 if distance(i) + weight(i,j) < distance(j) then14 distance(j) = distance(i) + weight(i,j)15 parent(j) = i这个算法的时间效率为O(V2)。
你可以使用堆来确定下一个要访问的顶点来获得O(E log V)的效率(这里的E是指边数 V是指顶点数)，但这样做会使程序变得复杂，并且在一个大而稀疏的图中效率只能提高一点点。
Sample Algorithm Execution考虑下面的图，图中的边可以用两种不同的方式表示:Edge Weight(1, 3) 5 (1, 4) 8 (3, 4) 2 (3, 5) 3 (4, 2) 3 (4, 6) 7 (5, 2) 6 (2, 6) 21 2 3 4 5 61 0 0 5 8 0 02 0 0 03 6 23 5 0 0 2 3 04 8 3 2 0 0 75 06 3 0 0 06 0 2 07 0 0这是问题的初始状态:更新这个表格,和顶点1相邻的有顶点3、4现在还没被访问的顶点中顶点3到源点的距离最小，所以它是下一个要被访问的点:和顶点3相邻的顶点有4、更新这些顶点: 现在还没被访问的顶点中顶点4到源点的距离最小，它的邻点有1、2、3、6, 因为别的点都已经被访问过了，所以只有顶点2、6需要被更新:在剩下的三个顶点(2, 5, 和 6)中, 顶点 5 最接近源点，所以要被访问。
它的邻点有2、3,只有顶点 2 没有被访问过。
经顶点 5 再到顶点 2 的距离是14,比经顶点 4 的路径长(那条长为10),所以顶点 2 不需要更新。
在剩下的两个顶点中最接近的是顶点 2 ，它的邻点是顶点 4、5、6,只有顶点 6 没被访问过。
另外顶点 6 要被更新:6 没被访问过，它所有的邻点都被访问过了:最后，只有顶点Sample Problem: Package Delivery投递包裹给出一个地点的集合，和连接它们的道路的长，和一个按排好的包裹要投递的地点的清单。
找出按顺序投递所有包裹的最短路程。
分析:对于每一次投递，使用 Dijkstra 算法来确定两个点间的最短路程。
如果要投递的次数超过 N，我们就用计算每对点之间的最短距离来代替计算每投递的最短路程，最后只用简单把每一次投递一路程相加就是答案。
Extended Problem: All Pairs, Shortest Paths每对点之间的最短路程这个扩展问题就是确定一个表格a：这里a i,j= 顶点 i 和 j 之间的最短距离，或者无穷大如果顶点 i 和 j 无法连通。
这个问题常常是其它大的问题的子问题，如投递包裹。
Dijkstra 算法确定单源最短路径的效率为O(N2)。
我们在每个顶点上执行一次的效率为O(N3)。
如果不要求输出路径，还有一个更简单的算法效率也是O(N3)The Floyd-Warshall AlgorithmFloyd-Warshall 算法用来找出每对点之间的最短距离。
它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。
注意单独一条边的路径也不一定是最佳路径。
∙从任意一条单边路径开始。
一个两点之间的距离是边的权，或者无穷大如呆两点之间没有国相连。
∙对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到v 比己知的路径更短。
如果是更新它。
∙不可思议的是，只要按排适当，就能得到结果。
∙想知道更多关于这个算法是如何工作的，请参考[Cormen, Leiserson, Rivest]第26章。
Pseudocode:# dist(i,j) is "best" distance so far from vertex i to vertex j# Start with all single edge paths.For i = 1 to n doFor j = 1 to n dodist(i,j) = weight(i,j)For k = 1 to n do # k is the `intermediate' vertexFor i = 1 to n doFor j = 1 to n doif (dist(i,k) + dist(k,j) < dist(i,j)) then# shorter path?dist(i,j) = dist(i,k) + dist(k,j)这个算法的效率是O(V3)。
它需要邻接矩阵来储存图。
这个算法很容易实现，只要几行。
即使问题是求单源最短路径，还是推荐使用这个算法，如果时间和空间允许(只要有放的下邻接矩阵的空间，时间上就没问题)。
Problem Cues如果问题要求最佳路径或最短路程，这当然是一个最短路径问题。
即使问题中没有给出一个图，如果问题要求最小的代价并且这里没有很多的状态，这时常常可以构造一个图。
最大的一点要注意的是:最短路径 = 搜索做某件事的最小代价。
Extensions如果图是不加权的，最短路径包括最少的边。
这种情况下用宽优搜索(BFS)就可以了。
如果图中有很多顶点而边很少，这样会比Dijkstra 算法要快(看例子Amazing Barn)如果充许负权边，那么Dijkstra 算法就错了。
幸运的是只要图中没有负权回路Floyd-Warshall 算法就不受影响(如果有负权回路，就可以多走几圈得到更小的代价)。
所以在执行算法之前必须要检查一下图。
可以再增加一些条件来确定最短路径(如，边少的路径比较短)。
只要用从距离函数中得到比较函数，问题就是一样的。
在上面的例子中距离函数包括两个值代价和边数。
两个值都要比较如果必要的话。
Sample ProblemsGraph diameter图的直径给出:一个无向无权的连通图,找出两点距离最远的顶点。
分析:找出所有点之间的最短距离，再找出最大的一个。
Knight moves爵士的移动给出:两个 N*N 的棋盘.确定一个爵士从一个棋盘移动到另一个所需的最少步数。