New Click here to Enroll for SIDBI MSME Expert Class by ex-GM, SBI on Nov 24

    Register

    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