dijkstra算法

Dijkstra算法

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。注意该算法要求图中不存在负权边。

设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

（1）初始时，S只包含起点D；U包含除D外的其他顶点，且U中顶点的距离为“起点D到该顶点的距离”（例如，U中顶点A的距离为[D,A]的长度，然后D和A不相邻，则A的距离为∞）
（2）从U中选出“距离最短的顶点K”，并将顶点K加入到S中；同时，从U中移除顶点K
（3）更新U中各个顶点到起点D的距离。之所以更新U中顶点的距离，是由于上一步中确定了K是求出最短路径的顶点，从而可以利用K来更新其他顶点到起点D的距离（例如，[D,A]的距离可能大于[D,K]+[K,A]的距离）
（4）重复步骤（2）和（3），直到遍历完所有顶点

https://blog.csdn.net/yalishadaa/article/details/55827681

dijkstra算法是什么？

迪杰斯特拉算法用来解决从顶点v0出发到其余顶点的最短路径，该算法按照最短路径长度递增的顺序产生所以最短路径。对于图G=（V，E），将图中的顶点分成两组：第一组S：已求出的最短路径的终点集合（开始为｛v0}）。第二组V-S：尚未求出最短路径的终点集合（开始为V-{v0}的全部结点）。堆优化思考该算法复杂度为n^2,我们可以发现，如果边数远小于n^2,对此可以考虑用堆这种数据结构进行优化，取出最短路径的复杂度降为O(1)；每次调整的复杂度降为O（elogn）；e为该点的边数，所以复杂度降为O((m+n)logn)。实现1、将源点加入堆，并调整堆。2、选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。3、处理与u相邻的，未被访问过的，满足三角不等式的顶点1):若该点在堆里，更新距离，并调整该元素在堆中的位置。2):若该点不在堆里，加入堆，更新堆。4、若取到的u为终点，结束算法；否则重复步骤2、3。

直观理解：单源点最短路径——Dijkstra算法

  Dijkstra算法是由荷兰计算机科学家 Edsger Wybe Dijkstra于1959年提出的单源点最短路径算法（SSSP:Single Souce Shortest Path）。是一个解决加权图（不含负权重的边）中从一个顶点到其余各个顶点最短路径问题的算法。Dijkstra算法是一个集 贪心算法 ， 广度优先搜索（BFS） 和 动态规划 于一身的最短路径算法。Dijkstra算法的主要特点是从起源点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接顶点，直到扩展到终点为止。   Dijkstra算法通过维护两个集合： (已求出最短路径的顶点)和 （未求出最短路径的顶点），每次迭代地从 中移除路径距离最小的点到集合 中，并通过这个新移入的点来更新 中各个顶点到源点的最短路径，直到集合 为空。下面我们通过一个例子来简单描述Dijkstra算法的过程。   假设我们有如下的图，其中顶点A未此次算法的起点：   首先我们需要初始化两个集合 和 ，以及 中每个顶点到源点的距离，若不直接于A相邻，结果置为正无穷∞。    Step 1： 从集合 中挑选出距离最小的点，这里会挑选出顶点F，集合 和 变更为： ， ，根据最新的 ，重新计算 中顶点到源点A的最短距离。    Step 2:： 从集合 中挑选出距离最小的点，这里会挑选出顶点E，集合 和 变更为： ， ，根据最新的 ，重新计算 中顶点到源点A的最短距离。    Step 3： 从集合 中挑选出距离最小的点，这里会挑选出顶点C，集合 和 变更为： ， ，根据最新的 ，重新计算 中顶点到源点A的最短距离。    Step 4： 从集合 中挑选出距离最小的点，这里会挑选出顶点D，集合 和 变更为： ， ，根据最新的 ，重新计算 中顶点到源点A的最短距离。    Step 5： 从集合 中挑选出距离最小的点，这里会挑选出顶点B，集合 和 变更为： ， ，根据最新的 ，重新计算 中顶点到源点A的最短距离。    Step 6： 从集合 中挑选出距离最小的点，这里会挑选出顶点G，集合 和 变更为： ， ，由于集合 为空，算法停止迭代，输出结果。   以上就是对Dijkstra算法的计算过程的简单描述。

求最短路径的dijkstra算法

最短路径dijkstra算法如下：Dijkstra迪杰斯特拉是一种处理单源点的最短路径算法,就是说求从某一个节点到其他所有节点的最短路径就是Dijkstra。资料拓展：迪杰斯特拉算法(Dijkstra)是由荷兰数腔计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其薯纳衫余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。Dijkstra算法一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。将T中顶点按递增的次序加入到S中，保证：从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度。每个顶点对应一个距离值。S中顶点：从V0到此顶点的长度。T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度。依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。初始时令S={V0},T=V-S={其余顶点}，T中顶点对应的距离值。若茄搭存在，d(V0,Vi)为弧上的权值。若不存在，d(V0,Vi)为∞。从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中。对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值。重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止。