阅读 57

狄克斯特拉算法 Dijkstra algorithm

要解决的问题

导航软件是如何找出两点之间最快路线的?

如果用图来描述,即:图中每个节点表示一个地点,每条边表示一条路线,这些边 有向 并且 有权重。要查找从起点到终点的最佳通路(“最佳”的定义是:构成这条通路的所有边的权重和最小)。

思路

基于广度优先搜索的办法。广度优先在处理社交网络问题时,每个节点被第一次访问,就是最短通路。但地图导航问题最大的不同是,当一个节点第一次被访问到,不一定是最短路径,比如下图的从A到B。所以必须要遍历所有通路,随时更新最小的通路。

升级的方法:狄克斯特拉算法 Dijkstra algorithm

  • 核心思想:对于某个节点,如果我们已经发现最优通路,那无需在将来的计算中再考虑这个节点。 狄克斯特拉算法用巧妙的方式,实现了这一点。直接上代码:
"""构造一个路线图"""

import random

class Node:
    def __init__(self,geo_id):
        self.geo_id = geo_id # 本地点的id
        self.neighbours = {} # 相邻地点集合(id:weight 格式)
        self.best_pre_neighbour_id = -1
    
    def __str__(self):
        return "{}:{}".format(self.geo_id,self.neighbours)

geo_num = 10
relation_num = 15
geo_nodes = []

# 生成所有表示地点的Node
for i in range(geo_num):
    geo_nodes.append(Node(i))

# 随机生成若干单向的路线
for i in range(relation_num):
    a_id = random.randint(0,user_num-1)
    b_id = random.randint(0,user_num-1)
    if a_id == b_id:
        continue
    a_node = geo_nodes[a_id]
    weight = random.random()
    a_node.neighbours[b_id] = weight # 权重weight表示为从a到b用时

for geo_node in geo_nodes:
    print(geo_node)
复制代码
import queue

def findGeoWithMinWeight(min_weights,finish):
    """找到当前min_weights中最小的节点(当前离source_id最快的地点)"""
    min_weight = 1
    min_node_id = None
    for (k,v) in min_weights.items():
        if k in finish:
            continue
        if v <= min_weight:
            min_node_id = k
            min_weight = v
#     print(min_node_id,min_weight)
    return min_node_id,min_weight


def updateWeight(geo_nodes,min_weights,node_id):
    """找到当前节点的所有相邻地点,更新其min_weights值"""
#     print(min_weights)
    for (k,v) in geo_nodes[node_id].neighbours.items():
        if min_weights.get(k) is None or min_weights[k] > min_weights[node_id]+v:
            min_weights[k] = min_weights[node_id] + v
            geo_nodes[k].best_pre_neighbour_id = node_id

def get_path(geo_nodes,target_id):
    print(target_id)
    if geo_nodes[target_id].best_pre_neighbour_id >=0:
        get_path(geo_nodes,geo_nodes[target_id].best_pre_neighbour_id)
        
    
            
def Dijkstra_process(geo_nodes,source_id,target_id):
    """
    @param geo_nodes- 所有地点对象的集合;source_id- 出发点id;target_id- 目标id
    @return void
    1. 初始化数据
    2. 循环
    """
    # min_weight指当前检测到的、从source_id到目标点的最快路径(即,最小weight之和。会一直更新。)
    min_weights ={}
    min_weights[source_id]=0
    
    # finish指所有已经找到min_weight的点的集合,一旦在其中就不参与计算了
    finish = set() 
    
    # 开始循环:
    while True:
        min_node_id,min_weight = findGeoWithMinWeight(min_weights,finish)
        if min_node_id is None or min_weight is None:
            break
        finish.add(min_node_id)
        updateWeight(geo_nodes,min_weights,min_node_id)
    
    print(finish)
    get_path(geo_nodes,target_id)
    
Dijkstra_process(geo_nodes,1,3)

复制代码

狄克斯特拉算法的特点体会:

  1. 明显有动态规划的思想,从众多局部最优解,到整体最优解。

  2. 体会和"三角形两边之和大于第三边"的关系:一个关键是findGeoWithMinWeight()方法

    • 假设mw[x] 是当前 mw 中的最小值,所以它小于等于任何其他一个 mw[xn]。
    • 假设存在另一个通路,通过xn达到 x,那么通路的权重总和为 mw[xn] + w[xn, x] ≥ mw[x]。所以我们可以得到一个结论:拥有最小 mw 值的结点 x 不可能再找到更小的 mw 值,可以把它加入集合finish,不在计算
    • 要实现这个结论就有一个前提:所有weight都是正数 或者都是负数,或者说单调变化
  3. 不断将与最小mw相连的点展开,填充mw[],然后再从mw[]中挑最小的。这有点像广度或深度优先搜索,保证全部遍历,不同的是广度或深度优先搜索每次挑的是队首或队尾。

应用

把边的权重从时间换成比如距离、价格,这样 Dijkstra 算法可以让用户找到地图任意两点之间的最短路线,或者出行的最低价格等等。

总结

  • 非加权图寻找最短路径,使用广度优先搜索
  • 加权图寻找最短路径,使用狄克斯特拉算法
  • 狄克斯特拉算法只适用于有向无环图(directed acyclic gragh,DAG)
  • 狄克斯特拉算法需要保证单调变化,所以负权边也不适用狄克斯特拉算法,如果图中包含负权边,需要使用贝尔曼-福德算法(Bellman-Ford algorithm)
关注下面的标签,发现更多相似文章
评论