计算机网络——实现路由算法

Posted on | In | 次阅读
Words count in article: 1k 字 | Reading time ≈ 4 min

实验目的

运用各种编程语言实现基于 Dijkstra 算法的路由软件。

实验环境

系统：Mac OS X 10.13.1
语言：Python 3.6.5
平台：pycharm
外部库：networkx，matplotlib

实验过程

代码设计

现Dijkstra算法的方法有很多种，为了在最短的代码内实现最好的效果，我选择了python来实现，借助networkx的有向图类DiGrapg接口实现了图的存储，通过自己实现的Dijkstra算法完成了搜索。

图的构造

我们这里借助networkx库里的DiGraph类来构造有向图。DiGraph存储有向图的边的形式为形如(s，d，w)的三元组形式，其中：

s: 边的起点；
d: 边的终点；
w: 边的代价.

考虑到操作的便捷性，我们使用一个path.txt文件来实现图的各个边的三元组的存储，path.txt的格式如下：
Alt text

定义好边的数据结构之后，我们利用networkx中的函数add_edge()来实现边的输入和图的构建

1
2
3
4
5
for line in open("path.txt","r"): #按行读取文件

data.append(line.strip('\n'))

for row in data:

    row=row.split(',') #分割三元组

    G.add_edge(eval(row[0]), eval(row[1]), weight=eval(row[2])

Dijkstra算法

算法实现的流程图如下：
Alt text

演示部分

networkx库同样集成了图的绘制函数，我们通过与matplotlib库的协同操作来完成图的搜索演示。
通过以下代码来实现图的分屏：

1
2
3
plt.figure(figsize=(14, 6))

plt.subplot(121)
plt.subplot(122)

通过以下代码来实现初始图的绘制：

1
2
pos = nx.spring_layout(G)
nx.draw_networkx(G, pos,node_size=300,node_color='#FFB5C5')

通过以下代码来实现图上搜索路径的绘制：

1
2
3
4
5
6
# 绘制非路径上的边

edges_not_in_path = list(set(G.edges()) - set(edges))
edgewidth = [G.get_edge_data(edge[0], edge[1])['weight']/30 for edge in edges_not_in_path]
nx.draw_networkx_edges(G, pos, edgelist=edges_not_in_path, edge_color='b',width=edgewidth)
# 绘制路径上的边

edgewidth = [G.get_edge_data(edge[0], edge[1])['weight']/30 for edge in edges]
nx.draw_networkx_edges(G,pos,edgelist=edges,edge_color='r',width=edgewidth)

执行结果

我们这里把网络类比为一个有向图，事实上路由的传输方向可以是双向的。
Alt text
其中，图‘Test Graph’即为初始图；
对于图‘The shortest path from 0 to 6’：

红色边：通过Dijkstra算法搜索到的最小代价路径；
蓝色边：未采纳的边；
边的粗细程度：边的权值，越细代表权值越小.

为了验证我们得到的路径是否是正确的答案，我们使用networkx库中标准的函数进行检验，代码如下：
answer=nx.dijkstra_path(G,source=start_node,target=end_node)
可以得到输出的answer路径如下，与我们的代码所得出的答案相同：
Alt text

代码附录

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
import networkx as nx

import matplotlib.pyplot as plt


#路由算法实现

def Dijkstra(G,start,end):

    RG = G.reverse()
    
    dist = {}
    
    previous = {}
    
    for v in RG.nodes():
        
        dist[v] = float('inf')
        
        previous[v] = 'none'
    
    dist[end] = 0
    
    u = end
    
    while u!=start:
    
        u = min(dist, key=dist.get)
    
        distu = dist[u]
    
        del dist[u]
        
        for u,v in RG.edges(u):
            
            if v in dist:
                
                alt = distu + RG[u][v]['weight']
                
                if alt < dist[v]:
                    
                    dist[v] = alt
                    
                    previous[v] = u
    
        path=(start,)
    
        last= start
    
        while last != end:
        
            nxt = previous[last]
        
            path += (nxt,)
        
            last = nxt
    
        return path




        #初始化图函数

def init(G):
    
    data = []
    
    for line in open("path.txt","r"): 
        #按行读取文件
        
        data.append(line.strip('\n'))
    
    for row in data:

        #分割三元组
          
        row=row.split(',')      
        G.add_edge(eval(row[0]), eval(row[1]), weight=eval(row[2]))
   
    return G



if __name__=="__main__":
    
    #路由算法实现
    
    G=nx.DiGraph()
    
    G=init(G)
    
    start_node = 0
    
    end_node = 6
    
    path=Dijkstra(G,start_node,end_node)

    #标准库函数检测

    answer=nx.dijkstra_path(G,source=start_node,target=end_node)

    print("nx.dijkstra_path's path:")

    for i in range(len(answer)-1):
    
        print(str(answer[i])+'->',end="")

    print(answer[i+1])


    
    # 构造最小权值边路径
    
    edges=[]
    
    for i in range(len(path)-1):
        
        edges.append((path[i],path[i+1]))

    

    #绘制初始图
    
    plt.figure(figsize=(14, 6))
    
    plt.subplot(121)
    
    plt.title("Test Graph")
    
    pos = nx.spring_layout(G)
    
    nx.draw_networkx(G, pos,node_size=300,node_color='#FFB5C5')

    

    #绘制最小路径结果
    
    plt.subplot(122)
    
    plt.title("The shortest path from %d to %d" % (start_node, end_node))
    
    nx.draw_networkx_nodes(G, pos=pos, node_size=300,node_color='#FFB5C5')

    

    # 绘制非路径上的边
    
    edges_not_in_path = list(set(G.edges()) - set(edges))
    
    edgewidth = [G.get_edge_data(edge[0], edge[1])['weight']/30 for edge in edges_not_in_path]
    
    nx.draw_networkx_edges(G, pos, edgelist=edges_not_in_path, edge_color='b',width=edgewidth)

    

    # 绘制路径上的边
    
    edgewidth = [G.get_edge_data(edge[0], edge[1])['weight']/30 for edge in edges]
    
    nx.draw_networkx_edges(G, pos, edgelist=edges, edge_color='r',width=edgewidth)

    

    #显示
    
    plt.show()
小手一抖⬇️