Use Python 3 to find the Shortest bath between two nodes (the start node and end
ID: 3755250 • Letter: U
Question
Use Python 3 to find the Shortest bath between two nodes (the start node and end node should be selected by the user) given a array of adjacency lists using Dynamic programming.
Where
index 0 is node i
index 1 is node j
index 2 is the weight of the edge between node i and j.
Example
Node_adjacency_List = [
[1 ,2 ,2.669279]
[1 ,12 ,2.445226]
[2, 1, 2.669279]
[2, 3, 4.183270]
[2 ,13 ,4.123552]
[3, 2, 4.183270]
[3, 4, 5.702186]
[3, 14, 6.003664]
[4, 3, 5.702186]
[4 ,5 ,6.922902]
[4 ,15, 7.663811]
]
note: Code as if the number of nodes could be very large
Explanation / Answer
#!/usr/bin/env python3
# Class to represent a graph
class Graph:
def __init__(self, vertices):
self.V = vertices # No. of vertices
self.graph = [] # default dictionary to store graph
# function to add an edge to graph
def addEdge(self, u, v, w):
self.graph.append([u, v, w])
# The main function that finds shortest distances from src to
# all other vertices using Bellman-Ford algorithm. The function
# also detects negative weight cycle
def BellmanFord(self, src, dest):
# Initialize distances from src to all other vertices
# as INFINITE
dist = {}
for i in self.graph:
dist[i[1]] = float("Inf")
dist[src] = 0
# Relax all edges |V| - 1 times. A simple shortest
# path from src to any other vertex can have at-most |V| - 1
# edges
for i in range(self.V - 1):
# Update dist value and parent index of the adjacent vertices of
# the picked vertex. Consider only those vertices which are still in
# queue
for u, v, w in self.graph:
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Check for negative-weight cycles. The above step
# guarantees shortest distances if graph doesn't contain
# negative weight cycle. If we get a shorter path, then there
# is a cycle.
for u, v, w in self.graph:
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
print("Graph contains negative weight cycle")
return
# print the distance
print("distance: %d" % dist[dest])
if __name__ == '__main__':
Node_adjacency_List = [[1, 2, 2.669279], [1, 12, 2.445226], [2, 1, 2.669279], [2, 3, 4.183270], [2, 13, 4.123552], [
3, 2, 4.183270], [3, 4, 5.702186], [3, 14, 6.003664], [4, 3, 5.702186], [4, 5, 6.922902], [4, 15, 7.663811]]
# finding the unique nodes from the above list
g = Graph(len(set(i[1] for i in Node_adjacency_List)))
for i in Node_adjacency_List:
g.addEdge(*i)
# Print the solution
i, j = map(int, (input('source destination :')).split())
g.BellmanFord(i, j)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.