toBeTheLight.github.io 荒原

阅读:《算法图解》(3)狄克斯特拉算法

2018-01-21
toBeTheLight

狄克斯特拉算法————寻找加权图中最短路径的算法。

第七章 狄克斯特拉算法

寻找加权图(带有权重的图)中最短路径的算法。

步骤

  • 书中:
    1. 找出最便宜节点,即可在最短时间内抵达的节点;
    2. 更新该节点的邻居的开销;
    3. 重复这个过程,直到对图中每个节点都这么做;
    4. 计算最终路径; 这个步骤说明并不是很清晰。
  • 实际运用:
    下方权重值皆为从起点到当前节点的权重值之和。
  1. 列出除起点外的所有节点;
  2. 对节点添加权重值,其中起点直接指向的节点的权重是能直接列出的,其他节点可列为∞(无穷);
  3. 找到目前权重最小的节点,重复步骤2,即列出此节点指向节点的权重(需途径当前节点),若已有权重,则与当前权重比较取较小值并更新,同时将当前节点标记为已操作。
  4. 找到目前未操作的权重最小的节点,重复上述步骤;
  5. 所有节点操作完毕后,即可得到达到终点的最小权重。
  6. 路径怎么找呢,在上述添加个更新权重的时候,应该记录到达此节点的上一个节点是谁,那么从终点向上即可得到当前的最短路径。

例子

狄克斯特拉算法

表格中双波浪线为删除

  1. 列出所有节点

    节点 起点至权重 上级节点 已操作
    B      
    C      
    D      
    E      
    F      
  2. 添加权重

    节点 起点至权重 上级节点 已操作
    B 5 A  
    C 0 A  
    D    
    E    
    F    
  3. 获取当前权重最小节点C,更新此节点的邻居节点的权重值。 即A->C->D:30、A->C->E:35,需经过B。 更新上级节点和将C标记为已操作

    节点 起点至权重 上级节点 已操作
    B 5 A
    C 0 A  
    D 30 C  
    E 35 C  
    F    
  4. 获取当前未操作的权重最小节点B,重复步骤3,发现此时A->B->D权重为5+15=20,A->B->E权重为5+20=25,都比已记录的DE权重小,需更新DE数据和DE上级节点。

    节点 起点至权重 上级节点 已操作
    B 5 A
    C 0 A
    D 30 20 C B  
    E 35 25 C B  
    F    
  5. 重复此步骤至除终点外所有节点都被操作获得:

    节点 起点至权重 上级节点 已操作
    B 5 A
    C 0 A
    D 20 B
    E 25 B
    F 35 E  

所以最短路线为A->B->E->F,最小权重为35。

限制

狄克斯特拉算法有一个使用限制,当存在负权边时会有问题,所以不适用负权边存在的情况。 可以尝试添加B->C为-7权重,此时操作完C后再操作B,C的权重会变成最小,而C已被标记为已操作,会有冲突。可使用贝尔曼-福特算法,没看。

补充

其基本原理是:每次新扩展一个距离最短的点,更新与其相邻的点的距离。当所有边权都为正时,由于不会存在一个距离更短的没扩展过的点,所以这个点的距离永远不会再被改变,因而保证了算法的正确性。不过根据这个原理,用Dijkstra求最短路的图不能有负权边,因为扩展到负权边的时候会产生更短的距离,有可能就破坏了已经更新的点距离不会改变的性质。

小结

  • 广度优先搜索用于在非加权图中查找最短路径。
  • 狄克斯特拉算法用于在加权图中查找最短路径。
  • 仅当权重为正时狄克斯特拉算法才管用。
  • 如果图中包含负权边,使用贝尔曼-福特算法。

疑问

《算法图解》一书中说此算法只适用于有向无环图,正权边的有环图并不会影响已操作的节点的权重,为什么不适用?

书籍纠错

作者说他写错了,是适用于正权边的有环图的。 链接在此


相关文章

Content