图论：Dijkstra算法
2019-09-26 本文已影响0人
_NewMoon
记9月23日学习Dijkstra算法
用邻接矩阵存储稠密图，邻接表存储稀疏图，该算法适用单源最短路问题，朴素的Dijkstra算法适用
于稠密图（n^2 ~= m）,堆优化版本的Dijkstra算法适用于稀疏图(n ~= m)
思路 : 用一个数组dist[] 记录每个点与1号点的距离，如果距离没有确定，则记为无穷大，dist[ 1 ] = 0(1号点与1号点的距离为0），之后分为三步：
1： 遍历图，找到一个未确定距离的点
2： 记录该点，并标记它已经被使用过
3： 用该点来更新其他点与1号点的距离，维护dist数组
