狄克斯特拉算法 狄克斯特拉算法包含4个步骤。 找出最便宜的节点,即可在最短时间内前往的节点。 对于该节点的邻居,检查是否有前往它们的更短路径,如果有,就更新其开销。 重复这个过程,直到对图中的每个节点都这样做了。 计算最终路径。 要计算非加权图中的最短路径,可使用广度优先搜索。要计算加权图中的最短路径,可使用狄克斯特拉算法。 狄克斯特拉算法只适用于有向无环图(directed acyclic graph, DAG)。 最短路径指的并不一定是物理距离,也可能是让某种度量指标最小。 不能...