dijkstra的最短路径算法

❶ dijkstra算法

Dijkstra算法是一种用于寻找图中源点到其他所有顶点最短路径的算法。核心思想是贪心策略，从起点开始，每次选择与起点距离最近且尚未访问的邻接顶点，重复此过程直至终点被访问。

按照路径长度递增顺序生成。图顶点集合被分为两部分：一部分已确定最短路径的顶点集合S（最初仅包含源顶点），另一部分尚未确定的顶点集合T。将T中顶点按路径长度递增次序加入S中，确保从源点到S中所有顶点的路径长度不超过T中任一顶点到源点的最短路径。

每个顶点对应两个距离值。S中的顶点表示从源点到该顶点的直接最短路径长度，T中的顶点表示从源点到该顶点通过S中顶点的最短路径长度。

基于上述原则，可以证明从源点到T中顶点Vk的路径长度，要么是直接路径的权值，要么是通过S中顶点构成的路径权值之和。

❷ 最短路径算法（Dijkstra）

Dijkstra（ 迪科斯特拉 ）算法是用来解决单源最短路径的算法，要求路径权值非负数。该算法利用了深度优先搜索和贪心的算法。

下面是一个有权图，求从A到各个节点的最短路径。

第1步：从A点出发，判断每个点到A点的路径（如果该点不能直连A点则距离值为无穷大，如果该点能和A直连则是当前的权值），计算完之后把A点上色，结果如下图:

第2步：从除A点之外的点查找到距离A点最近的点C，从C点出发查找其邻近的节点（除去已上色的点），并重新计算C点的邻近点距离A点的值，如图中B点，若新值（C点到A点的值+C点到该点的路径）小于原值，则将值更新为5，同理更新D、E点。同时将C标记为已经处理过，如图所示涂色。

第3步：从上色的节点中查找距离A最近的B点，重复第3步操作。

第4步： 重复第3步，2步，直到所有的节点都上色。

最后就算出了从A点到所有点的最短距离。

leetcode 743题

❸ 用dijkstra算法计算源点到个结点的最短路径....谢谢亲爱的朋友~ 详细答案

(这里描述的是从节点1开始到各点的dijkstra算法，其中Wa->b表示a->b的边的权值，d(i)即为最短路径值)
1． 置集合S={2,3,...n}, 数组d(1)=0, d(i)=W1->i(1,i之间存在边) or +无穷大(1.i之间不存在边) 2． 在S中，令d(j)=min{d(i),i属于S}，令S=S-{j}，若S为空集则算法结束，否则转3
3． 对全部i属于S,如果存在边j->i，那么置d(i)=min{d(i), d(j)+Wj->i}，转2

❹ 最短路径 - Dijkstra算法

算法每次都查找距离起始点最近的点，那么剩下的点距离起始点的距离一定比当前点大。

1.选定A节点并初始化，如上述步骤3所示

2.执行上述 4、5两步骤，找出U集合中路径最短的节点D 加入S集合，并根据条件 if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 来更新U集合

3.这时候 A->B, A->C 都为3，没关系。其实这时候他俩都是最短距离，如果从算法逻辑来讲的话，会先取到B点。而这个时候 if 条件变成了 if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' ) ，如图所示这时候A->B距离 其实为 A->D->B

思路就是这样，往后就是大同小异了
算法结束

（图片来源于网络）

Dijkstra算法保证能找到一条从初始点到目标点的最短路径，只要所有的边都有一个非负的代价值。在上图中，粉红色的结点是初始结点，蓝色的是目标点，而类菱形的有色区域则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的，因而形成探测过程（exploration）的边境（frontier）。因而Dijkstra算法可以找到一条最短的路径，但是效率上并不高。

数据结构--Dijkstra算法最清楚的讲解

❺ 怎样用DIJKSTRA算法设计最短路径

：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
2)算法步骤：
a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。
b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
c.以k为新考虑的中间点，修改U中各顶点的距离；

❻ 利用Dijkstra算法求下图中从顶点1到其它各顶点间的最短路径，按下面表格形式

v1到v2：10为最短路径；

v1到v3：7为最短路径；

v1到v4：8为最短路径；

v1到v5：v1-> v2 -> v5 =10+6= 16；v1v3v5=7+9=16;v1v4v6v5=8+5+2=15; 15为最短路径；

v1到v6：v1v2v3v6=10+2+9=21；v1v3v6=7+9=16；v1v4v6=8+5=13；13为最短路径；

v1到v7：v1v2v5v7=10+6+20=36；v1v3v5v7=7+9+20=36；v1v3v6v7=7+9+30=46；

v1v4v6v7=8+5+30=42；v1v4v6v5v7=35；35为最短路径

Dijkstra：

求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）。源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV）。当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2）。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（V*lgV + E）。

以上内容参考：网络-最短路径算法

❼ 迪杰斯特拉算法dijkstra算法详细步骤

一、定义Dijkstra算法（迪杰斯特拉算法）是很有代表性的最短路径算法，用于计算一个结点到其他结点的最短路径。该算法指定一个点（源点）到其余各个结点的最短路径，因此也叫做单源最短路径算法。该算法是由荷兰计算机科学家Edsger W.Dijkstra于1959年发表。
Dijkstra算法是一种用于计算带权有向图中单源最短路径算法，不存在回溯的过程，因此它还不适用于带有负权重的情况。如果权值存在负数，那么被派生出来的可能是更短的路径，这就需要过程可以回溯，之前的路径需要被更短的路径替换掉，而Dijkstra算法是不能回溯的，它的每一步都是以当前最优选择为前提的。
Dijkstra算法的思想是广度优先搜索（BFS） 贪心策略。对于计算非加权图中的最短路径，也可使用BFS算法。Dijkstra算法是对BFS算法的推广，以起始点为中心向外层层扩展，并且每一次都选择最优的结点进行扩展，直到扩展到终点为止。Dijkstra算法可以划归为贪心算法，下一条路径都是由当前更短的路径派生出来的更长的路径。
Dijkstra算法在很多专业课程中都作为基本内容有详细的介绍，如数据结构、图论、运筹学等。
二、演示例子例子1
第1步，创建距离表。第1列是结点名称，第2列是从起点A到对应结点的已知最短距离。开始我们并不知道A到其它结点的最短距离是多少，默认初始距离是无穷大。如图2-1-1所示：
图2-1-1
第2步，遍历起点A的所有相邻结点，找到起点A的邻接结点B和C。从A到B的距离是5，从A到C的距离是2，刷新距离表中起点A到各结点的最短距离(绿色表示刷新)。如图2-1-2所示。
图2-1-2
第3步，从图2-1-2距离表中找到从A出发距离最短的点，也就是结点C（最小距离是2）。遍历结点C的所有相邻结点，找到结点C的相邻结点D和F（A已经遍历过，不需要考虑）。从C到D的距离是1，所以A到D的距离是A-C-D=2 1=3；从C到F的距离是8；从A到F的距离是A-C-F=2 8=10。然后刷新距离表(绿色表示刷新)。如图2-1-3所示：
图2-1-3
第4步，从图2-1-3距离表中找到从A出发距离最短的点（红色结点C已经遍历过，不需要考虑），也就是结点D（最小距离是3）。遍历结点D的所有相邻结点，找到相邻结点B、E和F（C已遍历过，不考虑）。从A-C-D-B的距离是3 1=4；从A-C-D-E的距离是3 1=4；从A-C-D-F的距离是3 2=5。刷新距离表中起点A到各结点的最短距离。如图2-1-4所示。
图2-1-4
第5步，从图2-1-4距离表中找到从A出发距离最短的点（红色结点C、D已经遍历过，不需要考虑），也就是结点B和E（最小距离是4）。遍历结点B的所有相邻结点，找到相邻结点E(D遍历过，不考虑),从A-C-D-B-E的距离为10，比当前A到E的最小距离4要大，不考虑。遍历结点E的所有相邻结点，找到相邻结点G、B(D遍历过，不考虑),从A-C-D-E-G的距离为4 7=114,不考虑。如图2-1-5所示。
图2-1-5
第6步，从图2-1-5距离表中找到从A出发距离最短的点（红色结点B、C、D、E已经遍历过，不需要考虑），也就是结点F（最小距离是5）。从A-C-D-F-G的距离为8, 比当前最小距离11要小，刷新距离表。如图2-1-6所示。
图2-1-6
就这样，除终点以外的全部结点都已经遍历完毕，距离表中存储的是从起点A到所有结点的最短距离。
例子2
图2-2-1是原始连通图。
图2-2-1
用Dijkstra算法找出以A为起点的单源最短路径步骤如下：

步骤
集合S
集合Q
1
选择A到集合S={A}
此时最短路径A->A=0
以A为中间点，查找相邻点
Q={B,C,D,E,F,G}
A->-B=5
A->C=2
A->其它Q中结点=∞
发现A->C=2权值为最短
2
选择C到S={A,C}
此时最短路径A->A=0,A->C=2
以C为中间点，从A->C这条路径开始找
Q={B,D,E,F,G}
A->B=5(由第1步得到)
A->C->D=3
A->C->F=10
A->C->其它Q中结点=∞
在A到Q的结点中，发现A->C->D=3权值为最短
3
选择D到S={A,C,D}
此时最短路径A->A=0,A->C=2,A->C->D=3,
以D为中间点，从A->C->D这条路径开始找
Q={B,E,F,G}
A->C->D->B=4(比第1步的A->B=5要短，替换之)
A->C->D->E=4
A->C->D->F=5(比第2步的A->C->F=10要短，替换之)
A->C->D->G=∞
在A到Q的结点中，发现A->C->D->B=4或A->C->D->E=4权值为最短
4
选择B、E到S={A,C,D,B,E}
此时最短路径A->A=0,A->C=2,A->C->D=3,A->C->D->B=4,A->C->D->E=4,
以B、E为中间点，分别从A->C->D->B、从A->C->D->E路径开始找
Q={F,G}
A->C->D->E->G=11
A->C->D->F=5(从第3步获得)
在A到Q的结点中，发现A->C->D->F权值为最短
5
选择F到S={A,C,D,B,E,F}
此时最短路径A->A=0,A->C=2,A->C->D=3,A->C->D->B=4,A->C->D->E=4,A->C->D->F=5
以F为中间点，从,A->C->D->F这条路径开始找
Q={G}
A->C->D->F->G=8(比第4步的A->C->D->E->G=11要短，替换之)
6
选择G到S={A,C,D,B,E,F,G}
此时最短路径A->A=0,A->C=2,A->C->D=3,A->C->D->B=4,A->C->D->E=4,A->C->D->F=5,A->C->D->F->G=8
集合Q为空，查找完毕。

例子3
Dijkstra算法的执行过程：设初始集合S={s}, Q={t,y,x,z}. 源结点s为最左边的结点，每个结点中（圆圈中）的数值为该结点的最短路径的估计值（当前中间值）。黑色的结点属于集合S，白色的结点属于集合Q。每次从集合 S中选择最新加入的结点，分别计算并刷新与它直接相邻的结点的最短路径的估计值，然后从集合Q中选择最小估计值的结点，加入到集合S中。例如(b)中，集合Q中刷新后各结点的估计值为10，5，∞，∞，选择最小估计值为5的结点y，加入到集合S中, 接着计算并刷新结点y的相邻结点的最短路径的估计值。依次类推，直到集合Q中的所有结点全部加入到集合S中，算法结束。如图2-3-1所示。
图2-3-1
三、应用
一切能抽象成图或树的场景，如果要求最短路径，Dijkstra算法可考虑。比如，查找两个城市之间的最短路径；在地图中寻找两个地点之间的最短路径；在网络连接中为路由器寻找最短的传输路径等。