动态路由算法编程与测试

动态路由算法是一种根据网络中链路的状态和拓扑信息来动态计算路由的算法。其中，Dijkstra算法和距离矢量路由算法是两种常见的动态路由算法。

1. Dijkstra算法是一种单源最短路径算法，用于计算从一个源节点到其他所有节点的最短路径。它的基本思想是通过不断更新节点的距离值，从源节点开始逐步扩展，直到找到所有节点的最短路径。以下是一个使用Python实现Dijkstra算法的示例：

import sys

def dijkstra(graph, start):
    # 初始化距离字典，将起始节点的距离设为0，其他节点的距离设为无穷大
    distances = {node: sys.maxsize for node in graph}
    distances[start] = 0

    # 初始化已访问节点集合和未访问节点集合
    visited = set()
    unvisited = set(graph)

    while unvisited:
        # 选择当前距离最小的节点
        current = min(unvisited, key=lambda node: distances[node])

        # 更新与当前节点相邻节点的距离
        for neighbor, distance in graph[current].items():
            new_distance = distances[current] + distance
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance

        # 将当前节点标记为已访问，并从未访问集合中移除
        visited.add(current)
        unvisited.remove(current)

    return distances

# 测试
graph = {
    'A': {'B': 5, 'C': 3},
    'B': {'A': 5, 'C': 1, 'D': 3},
    'C': {'A': 3, 'B': 1, 'D': 2},
    'D': {'B': 3, 'C': 2}
}
start_node = 'A'
distances = dijkstra(graph, start_node)
print(distances)

2. 距离矢量路由算法是一种基于每个节点维护距离矢量表的算法。每个节点的距离矢量表记录了从当前节点到其他节点的最佳出口和距离。节点通过交换距离矢量表来更新路由信息。以下是一个使用Python实现距离矢量路由算法的示例：

import sys

def distance_vector_routing(graph, start):
    # 初始化距离矢量表，将起始节点的距离设为0，其他节点的距离设为无穷大
    distance_vector = {node: {'distance': sys.maxsize, 'next_hop': None} for node in graph}
    distance_vector[start]['distance'] = 0

    # 更新距离矢量表
    for _ in range(len(graph)):
        for node in graph:
            for neighbor, distance in graph[node].items():
                new_distance = distance_vector[node]['distance'] + distance
                if new_distance < distance_vector[neighbor]['distance']:
                    distance_vector[neighbor]['distance'] = new_distance
                    distance_vector[neighbor]['next_hop'] = node

    return distance_vector

# 测试
graph = {
    'A': {'B': 5, 'C': 3},
    'B': {'A': 5, 'C': 1, 'D': 3},
    'C': {'A': 3, 'B': 1, 'D': 2},
    'D': {'B': 3, 'C': 2}
}
start_node = 'A'
distance_vector = distance_vector_routing(graph, start_node)
print(distance_vector)