The input data file is coordinates(nodes). The distances between them are calculated and matched against a table to find transmission rates. The goal is to find optimal routing path to either of 2 stations. That is,a path with maximum transmission rate while minimizing total number of links. What will be the code to implement Bellman Ford algorithm for this ? start nodes/vertices, links/edges, and transmission rates are stored as excel file.
df = pd.read_csv ('Trans_rates_complete.csv')
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.edges = []
def add_edge(self, u, v, weight):
self.edges.append((u, v, weight))
class BellmanFord:
def __init__(self, graph, source):
self.graph = graph
self.source = source
self.distances = {vertex: float('inf') for vertex in graph.vertices}
self.distances[source] = 0
def run(self):
for i in range(len(self.graph.vertices) - 1):
for u, v, weight in self.graph.edges:
if self.distances[u] + weight < self.distances[v]:
self.distances[v] = self.distances[u] + weight
for u, v, weight in self.graph.edges:
if self.distances[u] + weight < self.distances[v]:
print("Negative cycle detected")
return
print("Shortest distances:", self.distances)
def get_shortest_path(self, destination):
path = []
while destination != self.source:
path.append(destination)
destination = self.predecessors[destination]
path.append(self.source)
return path[::-1]
i=0
vertices=[]
graph=[]
while i<len(df):
vertices.append(df.start_car)
u=df.start_car[i]
v=df.end_car[i]
weight=df.trans_rate[i]
graph.append([u,v,weight])
i=i+1
vertices.append('BS1')
vertices.append('BS2')
graph=Graph(vertices)
bf = BellmanFord(graph, 0)
bf.run()
print("Shortest path:", bf.get_shortest_path('BS1'))