retagged by
392 views

1 Answer

1 votes
1 votes

Both are True.

First one :A sub-path of a shortest path is a shortest path. This is the theorem and optimal structure property and basis of dijkstra algorithm .True

Second one:- If a graph G contains a negative-weight cycle, then some shortest paths may not exist. This is also true .

Ref: https://www2.cs.arizona.edu/classes/cs545/fall09/ShortestPath.prn.pdf

Related questions