图解算法（七）

古城微笑少年丶 2021-12-16 16:25 251阅读 0赞

## 狄克斯特拉算法 ##

广度优先搜索，它找出的是段数最少的路径。如果要给每一段加上时间（加权），为了找到最快的路径，可使用狄克斯特拉算法。

### 1.使用狄克斯特拉算法 ###

1.  找出最便宜的节点，即可在最短时间内前往的节点
2.  对于该节点邻居，检查是否有前往它们的更短路径，如果有，就更新其开销
3.  重复这个过程，知道对图中的每个节点都这样做了
4.  计算最终路径

### 2.实现算法 ###

graph = {}
    graph["start"] = {}
    graph["start"]["a"] = 6
    graph["start"]["b"] = 2
    print graph["start"].keys()
    print graph["start"]["a"]
    graph["a"] = {}
    graph["a"]["fin"] = 1
    
    graph["b"] = {}
    graph["b"]["a"] = 3
    graph["b"]["fin"] = 5
    graph["fin"] = {}
    
    infinity = float("inf")
    costs = {}
    costs["a"] = 6
    costs["b"] = 2
    costs["fin"] = infinity
    
    parents = {}
    parents["a"] = "start"
    parents["b"] = "start"
    parents["fin"] = None
    
    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
    processed = []
    
    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)

### 3.小结 ###

*  广度优先搜索用于非加权图中查找最短路径
 *  狄克斯特拉算法用于在加权图中查找最短路径
 *  仅当权重为正时狄克斯特拉算法才管用

转载于:https://www.cnblogs.com/winddogg/p/10825054.html