0
$\begingroup$

Are following statements valid?

  1. Shortest Path in an undirected graph can be found using BFS. Is DFS an option here? If DFS is not an option, why.

  2. Dijkstra's SPT works if there are no negative weights in a Digraph. This is because Dijkstra's is a greedy algorithm. Once a vertex is removed from Indexed Priority Queue, it is not added back,even though a negative edge gives shortest path to that vertex later on. Dijkstra works even if cycles exist in digraph

  3. If a digraph doesn't contain cycles, then Topological Sort Order SPT will give shortest path from a single vertex to all other vertices. In this approach negative weights in digraph will not affect the correctness of algorithm. This is because topological sort makes sure all the vertices are in the correct order despite having negative weights on some edges (but not all)

  4. If a digraph doesn't contain negative edge cycle, but has cycles and some negative weight edges then Bellman Ford is correct algorithm to use to solve Shortest Path problem.

  5. What is a fundamental algorithm to solve shortest path problem in digraphs? BFS? I think DFS can work too, with a minor tweak to reset seen flag for a given vertex.

$\endgroup$
  • $\begingroup$ What is an organic algorithm? $\endgroup$ – Tjaden Hess Jul 10 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.