跳转至

Dijkstra算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# -*- coding: utf-8 -*-
class Dijkstra(object):
    def __init__(self, G, s):
        self.vertexNum = len(G) #图中顶点个数
        self.G = G #图的邻接矩阵形式
        self.Q = range(self.vertexNum) #顶点集合
        self.d = {} #顶点的最短路径估计
        self.p = {} #顶点在最短路径树中的前驱结点

        for i in range(self.vertexNum): #初始化
            self.d[i] = 1000000
            self.p[i] = 'null'
        self.d[s] = 0

    def extract_min(self): #将顶点集合的d值作为优先级，实现最小优先队列的出队操作
        min_dist = 1000000
        min_index = None
        for vertex in self.Q:
            if self.d[vertex] < min_dist: #找到d值最小的顶点
                min_dist = self.d[vertex]
                min_index = vertex
        self.Q.remove(min_index) #将d值最小的顶点出队
        return min_index

    def relax(self, u, v): #松弛操作
        if self.d[v] > self.d[u] + self.G[u][v]:
            self.d[v] = self.d[u] + self.G[u][v]
            self.p[v] = u

    def run(self):
        i = 0
        while(self.Q):
            u = self.extract_min() #抽取顶点u
            for v in range(self.vertexNum):
                if G[u][v] == 0: 
                    continue
                self.relax(u, v)
            i = i + 1
            print '==第'.decode("utf-8").encode("gbk"), i, '轮:'.decode("utf-8").encode("gbk")
            print '每个顶点的最短路径估计依次如下:'.decode("utf-8").encode("gbk")
            print self.d
            print '每个顶点的前驱结点依次如下:'.decode("utf-8").encode("gbk")
            print self.p
            print '\n'

if __name__ == '__main__':
    G = [[0, 10, 0, 5, 0],
         [0, 0, 1, 2, 0],
         [0, 0, 0, 0, 4],
         [0, 3, 9, 0, 2],
         [7, 0, 6, 0, 0]]

    test = Dijkstra(G, 0)
    test.run()