Mykhailo Marufenko Mykhailo Marufenko - 5 days ago 7
Python Question

Smalest total weight in weighted directed graph

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?

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

Comments