Question

深入理解 Dijkstra 算法实现原理

Answer 1

（嗯，第一段是抄的，由于本人算法的基础比较薄弱，我会尽量用通俗易懂的语言来让大家理解本文）

参考博客: 数据结构--Dijkstra算法最清楚的讲解

大概就是这样一个有权图， Dijkstra 算法可以计算 任意节点 到 其他节点 的最短路径

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