1,815 views
1 1 vote
Consider a weighted, directed acyclic graph G = (V,E,w) in which edges that leave the source vertex s may have negative weights and all other edge weights are nonnegative. Does Dijkstra’s algorithm correctly compute the shortest-path weight δ(s,t) from s to every vertex t in this graph? Justify your answer

2 Answers

0 0 votes
In case of -ve weight edges, dijkstra's may or may not failed, depending on the source vertex and Graph structure.
0 0 votes
Dijkstra's algorithm can be applied on directed graphs that are having - ve edges , but in case if there is a negative cycle then dijkstra algorithm fails to provide correct solution.

in this question it is given a Directed Acyclic Graph which has a property that from any vertex if we take an outgoing edge then there will be no way to come back to that vertex again , that means there will be no cycle not even a positive weight cycle and no -ve weight cycle so in my opinion we can apply Dijkstras algorithm.
Position:
Show:

Related questions

6 6 votes
1 answers 1 answer
3.7k
3.7k views
vaishali jhalani asked Nov 5, 2016
3,719 views
What is the time complexity of Dijkstra’s algorithm if it is implemented using AVL Tree instead of Priority Queue over a graph G = (V, E)?
1 1 vote
1 answers 1 answer
1.4k
1.4k views
vaishali jhalani asked Nov 4, 2016
1,399 views
When the graph contain negetive weight edges but no negetive weight cycle, in this case can dijkstra leads to incorrect result?
1 1 vote
1 1 answer
1.6k
1.6k views
Souvik33 asked Dec 19, 2022
1,561 views
If a -ve weight cycle is reachable from source, the Dijkstra's algorithm gets into an infinite loop TRUEFALSE