Had problem with two quiz questions that I can\'t figure out. Would like to know
ID: 3556105 • Letter: H
Question
Had problem with two quiz questions that I can't figure out. Would like to know if I got them right or not. Please include also how sure you are of your answers. A lot of the time in the past, people gave me answers that ended up being wrong. Thanks a bunch for any guidance.
-----------------------------------
Which of the following graph algorithms is designed specifically to accept negative edge weights? Pick all that apply:
topological sort
Dijkstra's algorithm
Bellman-Ford algorithm
unweighted shortest path algorithm
Which of the following shortest path algorithms will work only with a DAG? Pick all that apply.
unweighted shortest path algorithm
Bellman-Ford algorithm
topological sort
Dijkstra's algorithm
a.topological sort
b.Dijkstra's algorithm
c.Bellman-Ford algorithm
d.unweighted shortest path algorithm
Explanation / Answer
1.
Bellman Ford algorithm
Bellman-Ford algorithm is an extension of dijkstra search algorithm so that it can handle negative edges.
Unweighted shortest path algorithm, and topological sort are independent of edges weights.
2.
Topological sort
Topological sort needs to find an ordering (precedence) which cannot work without directed acyclic graphs.
Unweighted shortest path algorithm, dijkstra search algorithm and Bellman-Ford algorithm are general shortest path search algorithms that will work are all graphs (Undirected and Directed graphs with cycles). All of them mark nodes when they are visited, so cycles is not a problem.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.