Question

For the Dijkstra's algorithm applying on a graph, which of the following condition is required?

• A. Graph must be directed acyclic
• B. Graph must not have negative edge weights
• C. All edges must have equal weight
• D. Graph must be complete

Hint:

Remember: Dijkstra = No Negatives. If you see a negative sign on an edge, put away Dijkstra's and pick up Bellman-Ford!

Answer 1

The Correct Option is B

Dijkstra's algorithm is a fundamental graph search algorithm used to find the shortest paths between nodes in a graph. However, its greedy nature imposes a specific constraint on the types of edge weights it can handle. 1. The Greedy Mechanism: Dijkstra's algorithm works by maintaining a set of "visited" nodes and greedily choosing the next node with the smallest known distance. It assumes that once a node is added to the visited set, the shortest path to that node has been found and will not change. 2. The Problem with Negative Weights: If a graph contains negative edge weights, the "greedy" assumption fails. A path that looks longer initially could potentially become shorter later by traversing a negative edge. Since Dijkstra's does not re-evaluate nodes once they are marked as visited, it may fail to find the true shortest path. 3. Evaluation of Conditions:
• Directed Acyclic Graph (DAG): While Dijkstra's works on DAGs, it is not a requirement. It works perfectly fine on graphs with cycles as long as weights are non-negative.
• Negative Edge Weights: This is the critical constraint. For the algorithm to guarantee correctness, the graph must not have negative edge weights.
• Equal Weights: If all edges have equal weights, the algorithm effectively becomes a Breadth-First Search (BFS). This is not a requirement.
• Complete Graph: A graph does not need to be complete for Dijkstra's to function. For graphs with negative edges, alternative algorithms like the Bellman-Ford algorithm must be used.