解释一下dijkstra算法这个计算过程的意思 怎么算的

最近也看到这个算法，不过主要是通过C语言介绍的，不太一样，但基本思想差不多。下面只是我个人的看法不一定准确。

Dijkstra算法主要解决指定某点(源点)到其他顶点的最短路径问题。

基本思想：每次找到离源点最近的顶点，然后以该顶点为中心(过渡顶点)，最终找到源点到其余顶点的最短路。

t=1：令源点(v_0)的标号为永久标号(0,λ)(右上角加点), 其他为临时(+无穷,λ) 就是说v_0到v_0的距离是0，其他顶点到v_0的距离为+无穷。t=1时，例53上面的步骤(2)(3)并不能体现

t=2：第1步v_0(k=0)获得永久标号，记L_j为顶点标号当前的最短距离(比如v_0标号(0,λ)中L_0=0), 边(v_k,v_j)的权w_kj 步骤(2)最关键，若v_0与v_j之间存在边，则比较L_k+w_kj与L_j, 而L_k+w_kj=L_0+w_0j<L_j=+无穷。

这里只有v_1,v_2与v_0存在边，所以当j=1,2时修改标号, 标号分别为(L_1, v_0)=(1, v_0), (L_2, v_0)=(4, v_0), 其他不变。步骤(3)比较所有临时标号中L_j最小的顶点, 这里L_1=1最小，v_1获得永久标号(右上角加点)。

t=3: 第2步中v_1获得永久标号(k=1), 同第2步一样，通过例53上面的步骤(2)(3)，得到永久标号。 步骤(2),若v_1与v_j(j=2,3,4,5(除去获得永久标号的顶点))之间存在边，则比较L_1+w_1j与L_j。这里v_1与v_2，v_3，v_,4存在边，

对于v_2, L_1+w_12=1+2=3<L_2=4, 把v_2标号修改为(L_1+w_12, v_1)=(3, v_1);

对于v_3, L_1+w_13=1+7=8<L_3=+无穷, 把v_3标号修改为(L_1+w_13, v_1)=(8, v_1);

对于v_4, L_1+w_14=1+5=6<L_4=+无穷, 把v_4标号修改为(L_1+w_14, v_1)=(6, v_1);

v_5与v_1不存在边，标号不变。步骤(3), 找这些标号L_j最小的顶点，这里v_2标号最小

t=4: k=2, 与v_2存在边的未获得永久标号的顶点只有v_4, 比较L_2+w_24=3+1=4<L_4=6, 把v_4标号修改为(L_2+w_24, v_2)=(4, v_2); 其他不变。步骤(3), L_4=4最小。

t=5: k=4, 同理先找v_4邻接顶点，比较，修改标号，找L_j最小

t=6: 同理

啰嗦的这么多，其实步骤(2)是关键，就是通过比较更新最短路径，右上角标点的就是距离源点最近的顶点，之后每一步就添加一个新的”源点”，再找其他顶点与它的最短距离。

迪杰斯特拉算法(Dijkstra)(百度百科)：

>

楼上正解，你找个图自己用此算法实践一下就知道了，从A点出发，发现离A最近的点是B点，那么我们就已经认为A到B的最短距离就是AB了，如果有负数，就指不定冒出个C点,AC+CB<AB;或者冒出个DE为很大的负值，AC+CD+DE+EF+FB<AB;等等诸如此类的情况。

简单说来，你驾车从家出发到某地沿某条路只需经过一个收费站，但是远在外省某地有个站不但不收你的费，你去了还会给你个千八百万的欢迎光临费，你能说你直接沿着这条路去某地是最省费用的？不计时间成本，绕到外省那个给你钱的地方，再绕回到你的目的地，还能赚钱呢。

而且一般权值为负的图研究也比较少。有些带负权的图，某些点间还没有最小距离呢。中间出个带某条负权很大的边的环圈，绕此一圈所经过的距离反而减少了，那就一直在此圈上绕啊绕啊绕到负的足够大溢出为止。

当然考虑各种自己随便假设出来的变种问题也是很有趣的。比如说边带有多个权值对应多次经过改变的消费，上面的问题有可能变成有解的。话说那个站会后悔，第二次经过它会收回100万，第三次经过收回250万，这样的话你只需要经过一次就够了，问题也是有解的。再比如说对于多权重图，从A点出发经过B点到达C点的最短路线，就不是简单的AB最短路线+BC最短路线了，说不定两者有重合边，第二次经过来个天价就傻眼了。其实这种图貌似应该可以转化成单权重图的，我直觉估计啊，刚随便想出这个问题，还没去思考这个问题的解^_^

以上就是关于解释一下dijkstra算法这个计算过程的意思 怎么算的全部的内容，包括:解释一下dijkstra算法这个计算过程的意思 怎么算的、vc环境 最短路径算法、dijkstra算法等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！