325 dijkstra算法1 #
- 问题描述
- 算法流程
问题描述 #
这个算法用于解决图中单源最短路径问题。所谓单源节点是指给定源节点，求图中其它节点到此源节点的最短路径。
算法流程 #
Dijkstra算法采用的是一种贪心的策略，它设定除了源节点外所有节点到源的距离为无穷大，然后逐步处理所有节点与当前节点的最短距离，
当所有节点更新完后，再回溯出最短路径
当所有节点更新完后，再回溯出最短路径
- 设定除源节点以外的其它所有节点到源节点的距离为INFINITE(一个很大的数)，且这些节点都没被处理过
- 从源节点出发，更新其余节点到源节点的距离。如果以某个节点到源节点的距离比之前的值更小，则更新此节点到源节点的距离，直到其余所有节点都处理完。
- 找到与当前源节点距离最近的点作为下一个源节点，将当前节点进行标记，下次更新路径时如遇到标记结点则跳过。重复2,3过程，直到所有点都被标记
- 由于处理节点时每次都是找下一个距离最近的节点，因此直接回溯处理时的路径即可获取目标路径
小结 #
习题 #
- 为什么更新结点时遇到已经标记的结点要跳过？
- dijkstra算法是最优解吗？
