时间戳

首页 > 技术文章 > 加权图与非加权图

加权图与非加权图

chiyun 2020-12-12 14:15 原文

1.加权图，非加权图

说白了，就是在有向图的边上加上数字，这个数字可以代表很多东西，如果边代表路径，那么数字可以代表这个边的长度。同时这个数字有专门的术语，叫做权重。要计算非加权图中的最短路径，可使用广度优先搜索。要计算 加权图中的最短路径，可使用狄克斯特拉算法。

image-20201211164212096

2.狄克斯特拉算法

狄克斯特拉算法是用来寻找一个加权图的最短路径。对于一个加权图来说，边最少不代表路程最短。

狄克斯特拉算法包含四个步骤

1 找出“最便宜”的节点，即可在最短时间内到达的节点。
2 更新该节点的邻居的开销，其含义将稍后介绍。
3 重复这个过程，直到对图中的每个节点都这样做了。
4 计算最终路径。

3.环

在处理图的问题时候，可能会遇到环，比如下图

image-20201211165043695

这意味着你可从一个节点出发，走一圈后又回到这个节点。假 设在下面这个带环的图中，你要找出从起点到终点的最短路径。

image-20201211165120117

当遇到环的时候，从图中我们可以看到当我们没绕环一次，都会加8的权重，甚至我们可以绕环多次，所以绕环的路径不可能是最短路径，我们应该避开环的路径。

且我们之前讨论到了无向图，其实无向图就是环。因为无向图意味着两个节点彼此指向对方。

image-20201211165310148

4.负权重

当加权图中出现了负权重，那么不能使用狄克斯特拉算法，比如下图，直接兑换海报不需要钱，兑换架子鼓需要35元，而先花5元买唱片，再换海报可以反赚2元，再换架子鼓，总需33元。

image-20201211180654458

如果对于上图这样的负加权图使用狄克斯特拉算法，根据其选择最小权的方案，他会选择第一种35元的方案。

在负权图中，要找出最短路径，可以使用另一种算法，贝尔曼-福德算法。

5.实现狄克斯特拉算法

利用迪克斯特拉算法实现下面的有向图

image-20201211184712200

根据该有向图的箭头我们可以知道各个节点之间的对应关系应该如下图

image-20201211184839950

随着算法的进行，costs和parents这两个散列表应该是变化的。

# graph表,构建加权图，对于graph表来说，是散列表嵌套散列表
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5

# 存储每个节点的开销，即消耗的路径,在python中可以使用infinity = float("inf")来表示无限大。
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity

# 存储父节点的散列表
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = None

# 存储已经处理过的节点，新建一个数组
processed = []

# 寻找最小开销节点
def find_min_node(costs):  # 寻找当前未被处理过且权重最小的节点
    min_weight = infinity
    min_node = None
    for k, v in costs.items():
        if k in processed:
            continue
        if v < min_weight:
            min_weight = v
            min_node = k

    return min_node

# 狄克斯特拉算法
def Dijkstra_algorithm():
    node = find_min_node(costs)  # 首先找到当前未被处理且权重最小的节点
    while node is not None:
        cost = costs.get(node)
        neighbors = graph.get(node)
        for k in neighbors:
            new_cost = cost + neighbors.get(k)
            if new_cost < costs.get(k):
                costs[k] = new_cost
                parents[k] = node
        processed.append(node)
        node = find_min_node(costs)


Dijkstra_algorithm()
print(costs)
print(parents)

推荐阅读