Question

Question 3 (20%) In this course we elaborated the Dijkstra algorithm for finding the shortest paths from one vertex to the other vertices in a graph. However, this algorithm has one restriction; It does not work for the graphs that have negative weight edges. For this question you need to search and find an algorithm for finding the shortest paths from one vertex to all the other vertices in a graph with negative weight edges. You need to explain step by step how the algorithm works and show one example and explain the results. Then compare it with Dijkestra in terms of complexity and implementation difficulties. Note: This question will be evaluated and marked based on how professional and comprehensive your answer is.

Answer 1

Time Complexity of the Given Algorithm is O(n*n)

Bellman ford algorithm it's follow dynamic approach to solve the edge one by one Algorithm: V --> number of Vertices d --> is the array to record each vertices. parent --> is the array to record it's parent's vertices //Initialized and parent's for u=0 to V: d[u]=infinity parent[u]=null d[source]=0 for i=1 to V-1: for each edge (u, v) with weight W: if d[u]+W < d[v] d[v]=d[u]+w parent[v]=u for each edge(u, v) with weight W if(d[u]+w<d[v]) print "Graph having negative cycle" return

i)The problem with dijkstra's algorithm was that it cannot processed through negative cycle as it's follow Greedy approach
ii)Where the Bellman ford follow dynamic it's solve the problem by take small pieces of the problem and merging them into one.It's change's the value at each step of iteration until the final result where find for each vertices