Smallest total weight in weighted directed graph

1
votes

There is question from one Quiz that I don't fully understand:

Suppose you have a weighted directed graph and want to find a path between nodes A and B with the smallest total weight. Select the most accurate statement:

  1. If some edges have negative weights, depth-first search finds a correct solution.

  2. If all edges have weight 2, depth-first search guarantees that the first path found to be is the shortest path.

  3. If some edges have negative weights, breadth-first search finds a correct solution.

  4. If all edges have weight 2, breadth-first search guarantees that the first path found to be is the shortest path.

Am I right that #1 is correct?

1
pythonalgorithmgraph
If you want us to answer quiz questions for you, we'll need you to explain your logic for the answer you chose. How did you arrive at that response, eliminating the other three? What did you find on your browser search for the topic? - Prune
Ok) If I right understand how weughted derected graph is built - than if we try to find smallest total weight then we should choose the easiest edges. So #2 and #4 - go out. #3 - I filtered because (again, if I right) the direct weighted graph contains lighter elements more deeply. - Mykhailo Marufenko
"direct weighted graph contains lighter elements more deeply" is incorrect, please review your text/papers/book/notes about directed graphs: its definition doesn't assert any specific sort - Roberto
I will, thanks Roberto, realy - Mykhailo Marufenko

1 Answers

2
votes

4 is the correct one!, because all edges have the same weight, so you need to find the node traversing the minimum quantity of edges.

1 Is wrong because depth-first search doesn't consider edge weights, so any node could be reached first