狄克斯特拉算法

狄克斯特拉算法(Dijkstra’s algorithm),用于计算加权图的最小总权重。
狄克斯特拉算法适用于有向无环图,且不能计算权重为负数的图。

图由节点和边组成。下图中,a、b、c是节点,a->b、b->c、c->a的有向箭头是边。
相连的节点称为邻居,下图中,b是a的邻居,c是b的邻居,a是c的邻居。


图.jpg

非加权图

边上不带权重的图称为非加权图(unweighted graph)。


非加权图.png

可以使用散列表(key/value)构建非加权图模型,模拟节点到邻居的映射关系:
• key为节点
• value为数组,存储节点的所有邻居节点
例如:

graph = {} #散列表(键值对)
graph["start"] = ["a","b"] # 节点a和节点b是起点start的邻居
graph["a"] = ["fin"] # 节点fin是节点a的邻居
graph["b"] = ["a","fin"] # 节点a、终点fin是节点b的邻居

广度优先搜索用于在非加权图中查找最短路径:从起点到终点经历的最少总边数。
如上图中最短路径为:起点->A->终点,或起点->B->终点,总边数为2。
而路径起点->B->A->终点,要经历3条边,不是最短路径。

加权图

边上带权重的图称为加权图(weighted graph)。


加权图.png

可以使用散列表(key/value)构建加权图模型,模拟节点到邻居的映射关系:
• key为节点
• value为散列表:key为节点的所有邻居,value为各个邻居的权重
例如:

graph = {} #用散列表构建图模型

graph["start"] = {} #用散列表表示起点start的所有邻居和相应的权重
graph["start"]["a"] = 6 #节点start的邻居:节点A的权重为6
graph["start"]["b"] = 2 #节点start的邻居:节点B的权重为2

graph["a"] = {} #用散列表表示节点A的所有邻居和相应的权重
graph["a"]["fin"] = 1 #节点A的邻居:终点fin的权重为1

graph["b"] = {} #用散列表表示节点B的所有邻居和相应的权重
graph["b"]["a"] = 3 #节点B的邻居:节点A的权重为3
graph["b"]["fin"] = 5 #节点B的邻居:终点fin的权重为5

graph["fin"] = {} #终点没有邻居
散列表模型图.png

实现狄克斯特拉算法

加权图.png
1、找到起点到其它所有节点边中,权重最小的节点。

从起点无法达到的节点,权重设为无穷大


第一步.png

此时找到权重最小的是节点B。
这意味着,从起点到节点B,最小权重为2,不可能有更小的权重了

代码如下

# 表示节点与权重的关系
infinity = float("inf") #表示无穷大
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

# 表示节点与父节点的关系
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

# 存储处理过的节点
processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf") #表示无穷大
    lowest_cost_node = None
    for node in costs:  # 遍历所有的节点
        cost = costs[node]
        if cost < lowest_cost and node not in processed:  # 如果当前节点的开销更低且未处理过,
            lowest_cost = cost  # 就将其视为开销最低的节点
            lowest_cost_node = node
    return lowest_cost_node
2、计算从起点前往该节点各个邻居的开销。

节点B的邻居:节点A、终点

【节点B】到【节点A】的权重:3
【起点】经【节点B】到【节点A】的权重:2+3=5
权重表中记录的【起点】到【节点A】的权重:6
6大于5,所以更新权重表中【节点A】的权重为5,父节点为【节点B】

【节点B】到【终点】的权重:5
【起点】经【节点B】到【终点】的权重:2+5=7
权重表中记录的【起点】到【终点】的权重:无穷大
无穷大于7,所以更新权重表中【终点】的权重为7,父节点为【节点B】

第二步.png
3、重复步骤1和2,直到处理过所有节点。

已处理过的节点,意味着已找到起点到该节点的最小权重,所以不用再次处理
起点和终点不处理

B节点已处理过。
除了B节点以外,权重最小的是节点A。

节点A的邻居:终点

【节点A】到【终点】的权重:1
【起点】经【节点A】到【终点】的权重:5+1=6
权重表中记录的【起点】到【终点】的权重:7
7大于6,所以更新权重表中【终点】的权重为6,父节点为【节点A】

重复第一步和第二步.png

代码如下

def dijkstras(graph, costs, parents):
    node = find_lowest_cost_node(costs) #在未处理的节点中找出权重最小的节点
    while node is not None: #这个while循环在所有节点都被处理过后结束
        cost = costs[node]
        neighbors = graph[node]
        for n in neighbors.keys(): #遍历当前节点的所有邻居
            new_cost = cost + neighbors[n]
            if costs[n] > new_cost: #如果经当前节点前往该邻居权重更小
                costs[n] = new_cost #就更新该邻居的权重
                parents[n] = node #同时将该邻居的父节点设置为当前节点
        processed.append(node) #将当前节点标记为处理过
        node = find_lowest_cost_node(costs) #找出接下来要处理的节点,并循环
4、确定最终路径

根据权重表,我们知道起点到终点的最小总权重为6
此时,找到终点的父节点:节点A
再找到节点A的父节点:节点B
节点B的父节点:起点
即找到总权重最小的路径:起点,节点B,节点A,终点

完整代码
# 建立图模型
graph = {} #用散列表构建图模型

graph["start"] = {} #用散列表表示起点start的所有邻居和相应的权重
graph["start"]["a"] = 6 #节点start的邻居:节点A的权重为6
graph["start"]["b"] = 2 #节点start的邻居:节点B的权重为2

graph["a"] = {} #用散列表表示节点A的所有邻居和相应的权重
graph["a"]["fin"] = 1 #节点A的邻居:终点fin的权重为1

graph["b"] = {} #用散列表表示节点B的所有邻居和相应的权重
graph["b"]["a"] = 3 #节点B的邻居:节点A的权重为3
graph["b"]["fin"] = 5 #节点B的邻居:终点fin的权重为5

graph["fin"] = {} #终点没有邻居

# costs
infinity = float("inf") #表示无穷大
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

# parents
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

# 存储处理过的节点
processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:  # 遍历所有的节点
        cost = costs[node]
        if cost < lowest_cost and node not in processed:  # 如果当前节点的开销更低且未处理过,
            lowest_cost = cost  # 就将其视为开销最低的节点
            lowest_cost_node = node
    return lowest_cost_node

def dijkstras(graph, costs, parents):
    node = find_lowest_cost_node(costs) #在未处理的节点中找出开销最小的节点
    while node is not None: #这个while循环在所有节点都被处理过后结束
        cost = costs[node]
        neighbors = graph[node]
        for n in neighbors.keys(): #遍历当前节点的所有邻居
            new_cost = cost + neighbors[n]
            if costs[n] > new_cost: #如果经当前节点前往该邻居更近,
                costs[n] = new_cost #就更新该邻居的开销
                parents[n] = node #同时将该邻居的父节点设置为当前节点
        processed.append(node) #将当前节点标记为处理过
        node = find_lowest_cost_node(costs) #找出接下来要处理的节点,并循环

dijkstras(graph, costs, parents)
print("最小总权重:", costs["fin"])
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。