狄克斯特拉算法的 Python 实现

我们用上图的例子来用 Python 实现狄克斯特拉算法

首先我们用代码实现三张散列表，Graph表、Costs表、Parents表：

Graph表

Graph表记录节点间的关系和权重。

Costs表

Costs表记录到达改节点的耗时。

Parents表

Parents表记录节点和父节点的关系。

---

创建 Graph 表

拿图的一部分为例，如起点和A点B点

graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph 为多个散列表的嵌套：

{
    'start': {'a': 6, 'b': 2}
}

获取 start 的相邻节点：

>>> graph['start'].keys()
dict_keys(['a', 'b'])

获取权重：

>>> graph['start']['a']
6
>>> graph['start']['b']
2

完整的 graph表是这样的：

# the graph
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph["a"] = {}
graph["a"]["fin"] = 1

graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5

graph["fin"] = {} # 没有相邻节点

# graph
{
    'start': {'b': 2, 'a': 6}, 
    'b': {'fin': 5, 'a': 3}, 
    'a': {'fin': 1}, 
    'fin': {}
    }

---

创建 Costs 表和 Parents 表

Costs 表：

# the costs table
infinity = float("inf") # 无限大
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

Parents 表：

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

最后创建一个数组记录已处理过的节点：

# 记录已处理的节点
processed = []

---

我们要实现的算法的思路流程图如下：

代码实现：

# the graph
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph["a"] = {}
graph["a"]["fin"] = 1

graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5

graph["fin"] = {}

# the costs table
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

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

processed = []


def find_lowest_cost_node(costs):
    """
    传入参数 costs 表
    根据当时 costs 表的记录返回消耗最低的节点
    """
    lowest_cost = float("inf")
    lowest_cost_node = None

    # 遍历 costs 表中各节点，找出消耗最低的
    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:
    # 从 costs 表中获得该节点的消耗
    cost = costs[node] 
    # 从 graph 表得到该节点的相邻节点
    neighbors = graph[node] 

    # 再用一个循环，遍历该节点的相邻节点
    for n in neighbors.keys():
        # 新节点的消耗 = 父节点的消耗 + 父节点到新节点的权重
        new_cost = cost + neighbors[n]
        # 如果新节点消耗比原来低
        if costs[n] > new_cost:
            # 更新 costs 表
            costs[n] = new_cost
            # 更新 parents 表
            parents[n] = node
    # 把节点记录为已处理
    processed.append(node)
    # 找到下一个要处理的节点
    node = find_lowest_cost_node(costs)

# 最后把 costs 表和 parents 表打印出来
print(costs)
print(parents)

执行结果：

{'fin': 6, 'b': 2, 'a': 5}
{'fin': 'a', 'b': 'start', 'a': 'b'}