狄克斯特拉算法、广度优先搜索、最短路径问题 python

朴灿烈づ我的快乐病毒、 2022-05-16 04:53 163阅读 0赞

--------------------

*  最短路径问题：使用广度优先搜索，使用图来建立问题模型
 *  假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。在Facebook,你与芒果销售商有联系吗?为此,你可在朋友中查找。
 *  查找最短路径，广度优先搜索可回答两类问题
    
     *  \[x\] 第一类问题:从节点A出发,有前往节点B的路径吗?(在你的人际关系网中,有芒果销 售商吗?)
     *  \[x\] 第二类问题:从节点A出发,前往节点B的哪条路径最短?(哪个芒果销售商与你的关系 最近?)

graph = {}
    graph["you"] = ["alice", "bob", "claire"]
    graph["bob"] = ["anuj", "peggy"]
    graph["alice"] = ["peggy"]
    graph["claire"] = ["thom", "jonny"]
    graph["anuj"] = []
    graph["peggy"] = []
    graph["thom"] = []
    graph["jonny"] = []

from collection import deque
    search_queue = deque()  # 创建一个队列
    search_queue += graph['you']  # 将你的邻居都加入到这个搜索队列中
    
    while search_queue:  # 只要队列不为空
        person = search_queue.popleft()  # 就取出其中的第一个人
        if person_is_seller(person):  # 检查这个人是否是芒果商
            print('{} is a mango seller!'.format('person')  # 是芒果商
            return True
        else:
            search_queue += graph[person]  # 不是芒果销售商。将这个人的朋友都加入搜索队列
    return False  # 如果到达了这里，就说明队列中没人是芒果商
    
    def person_is_seller(name):
        return name[-1] == 'm'

> 将一个人加入对列的时间是固定的O(1)，总时间就为O(人数)。所以广度优先搜索的运行时间为O(人数+边数)

--------------------

### 狄克斯特拉算法 ###

*  问题：其中每个数字表示的都是时间,单位分钟。为找出从起点到终点耗时最短的路径,你将使用 狄克斯特拉算法。

graph TD
        A[起点] -->|6| B(A)
        A[起点] -->|2| C(B)
        C -->|3| B
        B -->|1| D(终点)
        C -->|5| D(终点)

graph = {}
    
    graph["you"] = ["alice", "bob", "claire"]
    
    # 使用散列表
    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"] = {}  # 终点没有任何邻居
    
    
    infinity = float("inf")
    
    # 创建开销表
    infinity = float("inf")
    costs = {}
    costs["a"] = 6
    costs["b"] = 2
    costs["fin"] = infinity
    
    # 创建这个散列表
    parents = {}
    parents["a"] = "start"
    parents["b"] = "start"
    parents["fin"] = None
    
    # 存储处理过的节点
    processed = []
    
    # 代码
    node = find_lowest_cost_node(costs)  # 在未处理的节点中找出开销量最小的节点
    while node is not None:  # 这个while循环在所有节点都被处理过后结束
        cost = costs[node]
        neighbors = graph[node]
        for n in neighbors.key():  # 遍历当前节点
            new_cost = cost + neighbors[n]
            if costs[n] > new_costs:  # 如果经过当前节点前往该邻居更近
                costs[n] = new_costs  # 就更新该邻居的开销
                parents[n] = node  # 同时将该邻居的父节点设置为当前节点
        processed.append(node)  # 将当前节点标记为处理过
        node = find_lowest_cost_node(costs)  # 找出接下来要处理的节点
    
    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

*  第一步：找出最便宜的节点
 *  第二步：计算经起点的下一节点前往其各个节点所需的时间

## \- 第三步：重复 ##

*  重复第一步:找出可在最短时间内前往的节点。你对节点B执行了第二步,除节点B外,可在最短时间内前往的节点是节点A。
 *  重复第二步:更新节点A的所有邻居的开销。
 *  算法异同：
    
     *  使用广度优先搜索来查找两点之间的最短路径，这里的“最短路径”的意思是段数最少
     *  在狄克斯特拉算法中,你给每段都分配了一个数字或权重,因此狄克斯特拉算法找出的是总权重最小的路径。
 *  使用：
    
     *  要计算非加权图中的最短路径,可使用广度优先搜索。要计算加权图中的最短路径,可使用狄克斯特拉算法。
     *  狄克斯特拉算法只适用于有向无环图