By

Contents
  1. 1. 初始状态
  2. 2. 对单个点的处理
  3. 3. 完成算法（使用队列）
  4. 4. 记录路径
  5. 5. 总结

　　之前在做SDN网络控制器时，写过一个dijkstra的最短路径算法，现在回顾重温一下。
　　
　　以下面的图为测试样本：


　　
　　dijkstar算法的大致思想是（假设起点为A）：每新到达一个点V，探测所有与该点直接相邻的点（V’）及之间的距离d(V,V’)，如果V`是第一次探测到，那么记录其距离d(A,V’) = d(A,V) + d(V,V’)，如果已有记录但d(A,V) + d(V,V’)小于之前的记录，则更新记录；直到所有点都被遍历。
　　
　　依旧，为了方便，使用python语言，图用边的集合来表示：

1
2
g = [("A", "B", 6), ("A", "C", 3), ("B", "C", 2), ("B", "D", 5), ("C", "D", 3), ("C", "E", 4), ("D", "F", 3),
     ("D", "E", 2), ("E", "F", 6)]

　　

初始状态

　　从A开始探测，则已知距离d(A,A) = 0 。

对单个点的处理

1
2
3
4
5
6
7
8
9
10
11
map={"A":0} #初始记录
#对点"A"进行处理
for e in g:                 #遍历所有边 (e = edge)
    if "A" in e[0:2]:       #与A相连的边
        d = map["A"]+e[2]   #计算距离
        #添加记录（初始map为空，暂不考虑记录已存在的情况）
        if "A" == e[0]:     #无向边，需要确定另一顶点名称
            map[e[1]] = d
        else:
            map[e[0]] = d
print map

输出

1
{'A': 0, 'C': 3, 'B': 6}

　　一轮探测完以后，记录中新增了B C两点及它们与起点A的距离 ，那么接下来就要对B，C依次进行同样的处理了，随后对与B,C相连的点的处理……直到所有点处理完。

完成算法（使用队列）

　　对旧有代码进行改造：

  1. 将新探测到的点加入队列（待处理对象）
  2. 更新记录时与旧有记录作比较

　　增加以上功能后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
map={"A":0}
vp = Queue.Queue(maxsize=0)             #新建队列
vp.put("A")                             #初始化待处理点，将“A”加入队列
while(not vp.empty()):                  #队列不为空，执行
    v=vp.get()                          #取队首点v（vertex）
    for e in g:                         #遍历边集
        if v in e[0:2]:                 #边e与v相连        
            d = map[v]+e[2]             #计算A经由v到达v1的距离     
            if v == e[0]:               #无向边，需要确定另一顶点v1
                v1 = e[1]
            else:
                v1 = e[0]
            if v1 not in map:     #v1不在记录中（新探测到的点）
                vp.put(v1)        #v1加入队列尾（待处理点）
                map[v1] = d       #新增记录
            elif d < map[v1]:     #v1已在记录中，但新路径更短
                map[v1] = d       #更新记录
print map

输出为：

1
{'A': 0, 'C': 3, 'B': 5, 'E': 7, 'D': 6, 'F': 9}

将图拿来确认一下正确性。（算法到此已可算完成了。）

记录路径

　　以上只是输出了最短距离，但并没有记录路径，再稍微改造一下，并改以B为起点，并增加一些打印信息，方便了解算法运行过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
map={"B":["B",0]}
vp = Queue.Queue(maxsize=0)
vp.put("B")
#first step
while(not vp.empty()):
    v=vp.get()                          #对待处理点v，执行
    print "dealing with: "+v
    for e in g:                         #遍历边集
        if v in e[0:2]:                 #与v相连的边
            d = map[v][1]+e[2]          #计算距离
            if v == e[0]:               #无向边，需要确定另一顶点v1
                v1 = e[1]
            else:
                v1 = e[0]
            if v1 not in map:                   #v1不在记录中
                print "adding :"+v1
                map[v1] = [map[v][0]+v1,d]       #加入记录
                print map
                vp.put(v1)                      #将v1加入待处理点
            elif d < map[v1][1]:                #已有记录，但新路径更短
                print "update :"+v1
                map[v1] = [map[v][0]+v1,d]       #更新记录
                print map

输出为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
dealing with: B 
adding :A
{'A': ['BA', 6], 'B': ['B', 0]}
adding :C
{'A': ['BA', 6], 'C': ['BC', 2], 'B': ['B', 0]}
adding :D
{'A': ['BA', 6], 'C': ['BC', 2], 'B': ['B', 0], 'D': ['BD', 5]}
dealing with: A
dealing with: C
update :A
{'A': ['BCA', 5], 'C': ['BC', 2], 'B': ['B', 0], 'D': ['BD', 5]}
adding :E
{'A': ['BCA', 5], 'C': ['BC', 2], 'B': ['B', 0], 'E': ['BCE', 6], 'D': ['BD', 5]}
dealing with: D
adding :F
{'A': ['BCA', 5], 'C': ['BC', 2], 'B': ['B', 0], 'E': ['BCE', 6], 'D': ['BD', 5], 'F': ['BDF', 8]}
dealing with: E
dealing with: F

再次将图拿来确认一下正确性。

算法至此完成。

总结

　　dijkstar算法的正确性是如何保证的呢？因为算法在任一时刻，都保证了：

  1. 记录中的项是已探明路径中的最短路径。起始状态，结论显然成立：到自身距离为0。
  2. 探测了与所有当前点相邻的点（发现所有新路径）。对于新探测到的点，第一条路径也是唯一路径，自然是已知最短的；对于已有记录的点，则用更短路径（如果有）来更新；从而再次保证了1的成立。

　　当所有点都处理完，所有路径探明，记录自然就成为了到达所有点的最短路径。所以dijkstra算法其实是一个遍历所有路径，保留最小值的算法，只是选用了一个比较巧妙的遍历方式。

Contents
  1. 1. 初始状态
  2. 2. 对单个点的处理
  3. 3. 完成算法（使用队列）
  4. 4. 记录路径
  5. 5. 总结