📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!

  • google app store apple app store
  • ✖

      Question

      Does Dijkstra's algorithm work for graphs with both

      negative and positive edge weights?
      A Yes, it works for graphs with both negative and positive edge weights. Correct Answer Incorrect Answer
      B No, it only works for graphs with non-negative edge weights. Correct Answer Incorrect Answer
      C Yes, but it requires modifications to handle negative weights. Correct Answer Incorrect Answer
      D No, it only works for graphs with positive edge weights. Correct Answer Incorrect Answer
      E Yes, but it can result in incorrect shortest paths if negative weights are present. Correct Answer Incorrect Answer

      Solution

      Dijkstra's algorithm is a well-known algorithm for finding the shortest paths from a single source vertex to all other vertices in a graph. However, it assumes that all edge weights are non-negative. This is because Dijkstra's algorithm relies on the fact that once a vertex's shortest path is determined, it will not change. If there were negative weights, a shorter path might be found later, invalidating the correctness of the algorithm. For example, if a graph has a negative weight edge, Dijkstra's algorithm might incorrectly calculate the shortest path by not considering a path that includes the negative edge. This limitation is why Dijkstra’s algorithm is not suitable for graphs with negative edge weights. Instead, algorithms like Bellman-Ford are used for graphs where negative weights are present, as they can correctly handle such situations.

      Practice Next
      ask-question