22智能 狄克斯特拉算法复习

狄克斯特拉算法

1. 图 根据边有无方向分为： 有向图、无向图
   根据边有无权重变量分为： 有权图、无权图
   根据顶点是否连通分为： 连通图和非连通图
2. 入度：表示有多少条边指向该顶点
3. 出度：表示有多少条边从该顶点指出
4. 算法步骤：
   A. 找出权重最小的节点，即可在最短时间内到达的节点
   B. 更新该节点的邻居的开销
   C. 重复这个过程直到遍历所有节点
   D. 计算最终路径
5. 广度优先搜索查找两点之间的最短路径-段数最少；狄克斯特拉算法找出的是总权重最小的路径。
6. 狄克斯特拉算法只适用于有向无环图。
7. 不能将狄克斯特拉算法用于包含负权边的图。