Assignment|kruscul-路由算法模拟

算法介绍

选择python为编程语言编写Dijsktra算法。dilisktra算法的基本思想是：

[1] 以出发点初始化点的集合A

[2] 以未在A集合中的所有点为B集合

*[3] 找出A集合的所有点（依次取A中的点）到B集合中所有点（对于某一个A中的点，依次对B中的点进行判断）直接相连的情况（记录相连边的权+A中当前匹配的点到v0（起点）点的最短路径），记录A中的端点。(可简化)

[4] 比较路径后，找出B中可到达起点的最短路径（权最小）的点k，标记此路径。

[5] 将k从B中移去，加入A。

[6] 重复3-5直到B中无点。

[7] 每一个被标记的路径，都是起点到该点的最短路径。

下图是我选择的用于测试的路由图：

代码

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
class Vertex:
    # 顶点类
    def __init__(self, vid, outList):
        self.vid = vid  # 出边
        self.outList = outList  # 出边指向的顶点id的列表，也可以理解为邻接表
        self.know = False  # 默认为假
        self.dist = float('inf')  # s到该点的距离,默认为无穷大
        self.prev = 0  # 上一个顶点的id，默认为0

    def __eq__(self, other):
        if isinstance(other, self.__class__):
            return self.vid == other.vid
        else:
            return False

    def __hash__(self):
        return hash(self.vid)

class graph:
    def __init__(self, vertex, edges, v_set):
        self.vlist = vertex
        self.edges = edges
        self.vset = v_set

e_dict = dict()

def add_edge(front, back, value):
    e_dict[(front, back)] = value

# 创建顶点对象
v1 = Vertex(1, [2, 4])
v2 = Vertex(2, [4, 5])
v3 = Vertex(3, [1, 6])
v4 = Vertex(4, [3, 5, 6, 7])
v5 = Vertex(5, [7])
v6 = Vertex(6, [])
v7 = Vertex(7, [6])
add_edge(1, 2, 2)
add_edge(1, 4, 1)
add_edge(3, 1, 4)
add_edge(4, 3, 2)
add_edge(2, 4, 3)
add_edge(2, 5, 10)
add_edge(4, 5, 2)
add_edge(3, 6, 5)
add_edge(4, 6, 8)
add_edge(4, 7, 4)
add_edge(7, 6, 1)
add_edge(5, 7, 6)
v_list = [False, v1, v2, v3, v4, v5, v6, v7]
vset = set([v1, v2, v3, v4, v5, v6, v7])
g = graph(v_list, e_dict, vset)

def get_unknown_min():  # 此函数则代替优先队列的出队操作
    the_min = 0
    the_index = 0
    j = 0
    for i in range(1, len(g.vlist)):
        if (g.vlist[i].know is True):
            continue
        else:
            if (j == 0):
                the_min = g.vlist[i].dist
                the_index = i
            else:
                if (g.vlist[i].dist < the_min):
                    the_min = g.vlist[i].dist
                    the_index = i
            j += 1
    # 此时已经找到了未知的最小的元素是谁
    vset.remove(g.vlist[the_index])  # 相当于执行出队操作
    return g.vlist[the_index]

def main():
    # 将v1设为顶点
    v1.dist = 0

    while (len(vset) != 0):
        v = get_unknown_min()
        print(v.vid, v.dist, v.outList)
        v.know = True
        for w in v.outList:  # w为索引
            if (g.vlist[w].know is True):
                continue
            if (g.vlist[w].dist == float('inf')):
                g.vlist[w].dist = v.dist + g.edges[(v.vid, w)]
                g.vlist[w].prev = v.vid
            else:
                if ((v.dist + g.edges[(v.vid, w)]) < g.vlist[w].dist):
                    g.vlist[w].dist = v.dist + g.edges[(v.vid, w)]
                    g.vlist[w].prev = v.vid
                else:  # 原路径长更小，没有必要更新
                    pass

def real_get_traj(start, index):
    traj_list = []

    def get_traj(index):  # 参数是顶点在vlist中的索引
        if (index == start):  # 终点
            traj_list.append(index)
            print(traj_list[::-1])  # 反转list
            return
        if (g.vlist[index].dist == float('inf')):
            print('从起点到该顶点根本没有路径')
            return
        traj_list.append(index)
        get_traj(g.vlist[index].prev)

    get_traj(index)
    print('该最短路径的长度为', g.vlist[index].dist)

if __name__ == '__main__':
    main()
    real_get_traj(1, 3)
    real_get_traj(1, 6)