Mike Zhang

DNS DevOps CISSP CISA Security+ 摄影 程序员 北京

Dijkstra算法

06 Sep 2018 » algorithm

算法主要是用于加权图中两点之间的最短路径,如果是普通图,使用广度优先算法即可实现查找最少路径。但是下面的加权图中,如果是从0到8,直接使用广度优先的话则是0->7->8,而该路径上总耗时为15, 如果我们选择耗时最少的话应该是从0->1->2->8 总耗时为14,Dijkstra算法就是获取最佳的路径的算法。

Dijkstra算法的主要是步骤如下:

  • 1.找到最便宜的节点,最短时间到达的节点
  • 2.更新节点的邻居开销
  • 3.重复这个过程,对于图中每个点都这么做 (获得到达每个节点的最短开销)
  • 4.计算最终路径

该算法只适用于有向无环图,无向图指的是彼此指向对方,也就是存在环路的图。Dijstra算法中每条边都有关联数字的图,这些数字称为权重,带权重的图称为加权图

对于负权重的加权图,不能使用Dijkstra算法,应该使用贝尔曼-福德算法, 默认情况下,Dijkstra算法不认为已经构建好的最短路径会沿着同样的路径下重新获得最短的路径,路径只会增加不会出现缩减, 这也是该算法速度快的一个原因

具体实现

如下的实例为一个简单的加权图,获得从起点到终点的最佳路径,使用Dijkstra算法实现

graph LR
Start[起点] -->|2 |B(B)
Start[起点] -->|6 |A(A)
A[A] -->|1 |End(终点)
B[B] -->|5 |End(终点)
B[B] -->|3 |A(A)

具体的python代码如下,首先构建一个有向图,按照上述的设计,创建图的数据结构,每一个

graph = {}

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

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

graph["fin"] ={}

有向图设计完成后需要创建两个hash表用于,保存最终的路径和已经处理过的节点,parents和costs中保存了初始的状态,costs保存所有节点到起始节点的路径长度,后期进行动态的修改。代码如下,

infinity = float("inf")

costs = {}
costs["a"] = 6
costs["b"] =2 
costs["fin"] = infinity

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

processed = []

定义一个函数获得每个节点的最短距离的节点并返回

def find_lowest_cost_node(costs):
  lowest_cost = infinity
  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

获取Dijkstra算法的主要部分代码如下:

node = find_lowest_cost_node(costs)

while node is not None:
  cost = costs[node]
  neighbors = graph[node]
  print neighbors
  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 parents

Related Posts