1,191 views
1 votes
1 votes
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 votes
0 votes
In case of -ve weight edges, dijkstra's may or may not failed, depending on the source vertex and Graph structure.
0 votes
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.

Related questions

6 votes
6 votes
1 answer
1
vaishali jhalani asked Nov 5, 2016
3,038 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 votes
1 votes
1 answer
2
vaishali jhalani asked Nov 4, 2016
1,076 views
When the graph contain negetive weight edges but no negetive weight cycle, in this case can dijkstra leads to incorrect result?
1 votes
1 votes
1 answer
3
Souvik33 asked Dec 19, 2022
707 views
If a -ve weight cycle is reachable from source, the Dijkstra's algorithm gets into an infinite loop TRUEFALSE