Mykhailo Marufenko - 6 months ago 56

Python Question

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:

- If some edges have negative weights, depth-first search finds a correct solution.
- If all edges have weight 2, depth-first search guarantees that the first path found to be is the shortest path.
- If some edges have negative weights, breadth-first search finds a correct solution.
- 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?

Answer

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

Source (Stackoverflow)