99 lines
3.7 KiB
Python
99 lines
3.7 KiB
Python
|
import heapq
|
||
|
|
|
||
|
|
class LinkStateNetwork:
|
||
|
|
def __init__(self):
|
||
|
|
self.graph = {}
|
||
|
|
|
||
|
|
def add_edge(self, src, dest, weight):
|
||
|
|
if src not in self.graph:
|
||
|
|
self.graph[src] = {}
|
||
|
|
if dest not in self.graph:
|
||
|
|
self.graph[dest] = {}
|
||
|
|
self.graph[src][dest] = weight
|
||
|
|
self.graph[dest][src] = weight # Undirected graph
|
||
|
|
|
||
|
|
def dijkstra(self, start):
|
||
|
|
distances = {node: float('inf') for node in self.graph}
|
||
|
|
distances[start] = 0
|
||
|
|
priority_queue = [(0, start)]
|
||
|
|
shortest_paths = {node: [] for node in self.graph}
|
||
|
|
|
||
|
|
while priority_queue:
|
||
|
|
current_distance, current_node = heapq.heappop(priority_queue)
|
||
|
|
if current_distance > distances[current_node]:
|
||
|
|
continue
|
||
|
|
for neighbor, weight in self.graph[current_node].items():
|
||
|
|
distance = current_distance + weight
|
||
|
|
if distance < distances[neighbor]:
|
||
|
|
distances[neighbor] = distance
|
||
|
|
shortest_paths[neighbor] = shortest_paths[current_node] + [current_node]
|
||
|
|
heapq.heappush(priority_queue, (distance, neighbor))
|
||
|
|
return distances, shortest_paths
|
||
|
|
|
||
|
|
def print_routing_table(self, start):
|
||
|
|
distances, paths = self.dijkstra(start)
|
||
|
|
print(f"Link-State Routing Table from {start}:")
|
||
|
|
for destination in distances:
|
||
|
|
if distances[destination] < float('inf'):
|
||
|
|
print(f"To {destination} via {' -> '.join(paths[destination] + [destination])}, cost: {distances[destination]}")
|
||
|
|
else:
|
||
|
|
print(f"To {destination}: Unreachable")
|
||
|
|
|
||
|
|
# Example usage of Link-State
|
||
|
|
if __name__ == "__main__":
|
||
|
|
link_state_network = LinkStateNetwork()
|
||
|
|
link_state_network.add_edge('A', 'B', 1)
|
||
|
|
link_state_network.add_edge('A', 'C', 4)
|
||
|
|
link_state_network.add_edge('B', 'C', 2)
|
||
|
|
link_state_network.add_edge('B', 'D', 5)
|
||
|
|
link_state_network.add_edge('C', 'D', 1)
|
||
|
|
link_state_network.print_routing_table('A')
|
||
|
|
|
||
|
|
class DistanceVectorNetwork:
|
||
|
|
def __init__(self):
|
||
|
|
self.graph = {}
|
||
|
|
self.distance_table = {}
|
||
|
|
|
||
|
|
def add_edge(self, src, dest, weight):
|
||
|
|
if src not in self.graph:
|
||
|
|
self.graph[src] = {}
|
||
|
|
if dest not in self.graph:
|
||
|
|
self.graph[dest] = {}
|
||
|
|
self.graph[src][dest] = weight
|
||
|
|
self.graph[dest][src] = weight # Undirected graph
|
||
|
|
|
||
|
|
def initialize_distance_table(self, start):
|
||
|
|
for node in self.graph:
|
||
|
|
self.distance_table[node] = {n: float('inf') for n in self.graph}
|
||
|
|
self.distance_table[start][start] = 0
|
||
|
|
for neighbor in self.graph[start]:
|
||
|
|
self.distance_table[start][neighbor] = self.graph[start][neighbor]
|
||
|
|
|
||
|
|
def update_distance_table(self):
|
||
|
|
for _ in range(len(self.graph) - 1):
|
||
|
|
for src in self.graph:
|
||
|
|
for dest in self.graph[src]:
|
||
|
|
for neighbor in self.graph[src]:
|
||
|
|
if self.distance_table[src][dest] > self.distance_table[src][neighbor] + self.distance_table[neighbor][dest]:
|
||
|
|
self.distance_table[src][dest] = self.distance_table[src][neighbor] + self.distance_table[neighbor][dest]
|
||
|
|
|
||
|
|
def print_routing_table(self, start):
|
||
|
|
self.initialize_distance_table(start)
|
||
|
|
self.update_distance_table()
|
||
|
|
print(f"Distance Vector Routing Table from {start}:")
|
||
|
|
for destination in self.distance_table[start]:
|
||
|
|
if self.distance_table[start][destination] < float('inf'):
|
||
|
|
print(f"To {destination}: Cost: {self.distance_table[start][destination]}")
|
||
|
|
else:
|
||
|
|
print(f"To {destination}: Unreachable")
|
||
|
|
|
||
|
|
# Example usage of Distance Vector
|
||
|
|
if __name__ == "__main__":
|
||
|
|
distance_vector_network = DistanceVectorNetwork()
|
||
|
|
distance_vector_network.add_edge('A', 'B', 1)
|
||
|
|
distance_vector_network.add_edge('A', 'C', 4)
|
||
|
|
distance_vector_network.add_edge('B', 'C', 2)
|
||
|
|
distance_vector_network.add_edge('B', 'D', 5)
|
||
|
|
distance_vector_network.add_edge('C', 'D', 1)
|
||
|
|
distance_vector_network.print_routing_table('A')
|