[What]算法图解_狄克斯特拉算法

广度优先搜索寻找的是最短路径,而 狄克斯特拉算法(Dijkstra's algorithm) 用于找出最快的路径。

就像地图路径搜索一样,广度优先搜索代表“最少换乘”,狄克斯特拉算法代表“最快到达目的地”

术语

  • 权重(weight) : 为图中的每条边都关联一个数字
    • 比如在地图路径上每条边标明时间
  • 加权图(weighted graph) : 带权重的图
    • 计算加权图中的最短路径,使用 狄克斯特拉算法
  • 非加权图(unweighted graph) : 不带权重的图
    • 计算非加权图中的最短路径,使用 广度优先搜索
  • 环:当两个节点互为邻居时就称为环
    • 无向图中的 每一条边都是环
    • 狄克斯特拉算法 只适用于有向无环图(directed acyclic graph, DAG)
  • 负权边: 一个边的权重为负
    • 使用 贝尔曼-福德算法(Bellman-Ford algorithm) 处理这种情况
    • 不能将狄克斯特拉算法用于包含负权边的图,因为已经处理过的同级节点不会再纳入计算

狄克斯特拉算法执行步骤

  1. 从起始点找出到其他节点的时间以及父节点,存到列表中。(除邻居节点外,其余时间都是无穷大)
  2. 找出时间最短的邻居节点,并更新节点对应的时间值
  3. 对该节点的邻居进行检查是否有前往它们的最短路径,如果有就更新其开销,以及更新其对应父节点
  4. 重复步骤2,直到每个节点都检查完了
  5. 根据到达终点的路径关系计算最终路径
Last Updated 2018-10-14 日 19:32.
Render by hexo-renderer-org with Emacs 26.1 (Org mode 9.1.14)