1、引入
上篇博文中讲述了广度优先搜索的算法,主要解决是否存在A->B和A->B路径最短的问题。广度优先搜索仅仅是解决了图边数最少的路径,假如边上附有权值,要找出最快的路径,那此时可使用狄克斯特拉算法。
2、狄克斯特拉算法
关键理念:
找出图中最便宜的节点,并确保没有该节点的更便宜的路径!
作用:
能够找出加权图中前往X的最短路径!
适用场合:
只适合有向无环图!!!不适合无向图和有向有环图。
有向无环图边的权重都要是非负数!!!边的权重为负数的可以参考:贝尔曼-福德算法(Bellman-Ford algorithm)。
名词解释:
最短路径:指的并不一定是物理物理,也可能是让某种度量指标最小