本文内容学习自 Aditya Bhargava 的《算法图解》

图论领域中的狄克斯特拉算法包含4个步骤。
(1) 找出最便宜的节点,即可在最短时间内前往的节点。
(2) 对于该节点的邻居,检查是否有前往它们的更短路径,如果有,就更新其开销。
(3) 重复这个过程,直到对图中的每个节点都这样做了。
(4) 计算最终路径。



要计算非加权图中的最短路径,可使用广度优先搜索。要计算加权图中的最短路径,可使用狄克斯特拉算法。
在无向图中,每条边都是一个环。狄克斯特拉算法只适用于有向无环无负权边的图
狄克斯特拉算法这样假设:对于处理过的海报节点,没有前往该节点的更短路径。这种假设仅在没有负权边时才成立。因此,不能将狄克斯特拉算法用于包含负权边的图。在包含负权边的图中,要找出最短路径,可使用另一种算法——贝尔曼-福德算法(Bellman-Ford)

youtube video

python code:

#!/usr/local/bin/python3
# -*- coding: UTF-8 -*-

graph = {}
graph["start"] = {}
graph["start"]["A"] = 6
graph["start"]["B"] = 2
graph["A"] = {}
graph["A"]["end"] = 1
graph["B"] = {}
graph["B"]["A"] = 3
graph["B"]["end"] = 3
graph["end"] = {}

infinity = float("inf")
costs = {}
costs["A"] = 6
costs["B"] = 2
costs["end"] = infinity

parents = {}
parents["A"] = "start"
parents["B"] = "start"
parents["end"] = 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

node = find_lowest_cost_node(costs)

while node is not None:
    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)

print( graph )
print("============================")
print( costs )
print("============================")
print( costs["end"] )


 

分类: AlgorithmPython

发表评论

电子邮件地址不会被公开。 必填项已用*标注