Question:
Dijkstra's algorithm fails for graphs with _______.
Dijkstra's algorithm fails for graphs with _______.
Show Hint
When working with graphs that have negative edge weights, use the Bellman-Ford algorithm instead of Dijkstra’s algorithm, as it handles negative weights.
Updated On: Jun 16, 2025
- Negative weights
- Disconnected components
- Directed edges
- Self-loops
Show Solution
Verified By Collegedunia
The Correct Option is A
Solution and Explanation
Dijkstra's algorithm is based on the assumption that all edge weights are non-negative. If a graph contains negative weights, Dijkstra’s algorithm may not work correctly because it doesn't handle situations where a path to a vertex becomes shorter after a vertex is already processed.
Hence, Dijkstra's algorithm fails in graphs with negative edge weights.
Was this answer helpful?
0
0
Top AP PGECET Computer Science & Information Technology Questions
Digital signatures provide ________.
- Let \( A = \{1, 2, 3\} \). Which of the following is the number of distinct relations on \( A \)?
- Let \(A, B\) be two events and \(\overline{A}\) be the complement of \(A\). If \(P(A) = 0.7\), \(P(B) = 0.7\) and \(P(B \mid A) = 0.5\), then \(P(A \cup B) = \_\_\_.\)
A Session variable is created ________.
- Which is the correct syntax to link XML file with CSS?
View More Questions
Top AP PGECET Graph Theory Questions
- A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, \( n \) is _______.
- Assume G is a simple undirected graph and some vertices of G are of odd degree. Add a node \( v \) to G and make it adjacent to each odd degree vertex of G, then the resultant graph is sure to be _______.
- A subgraph H of a graph G is called a clique if _______.
- For a given graph G having \( v \) vertices and \( e \) edges which is connected and has no cycles, which of the following statements is true?
The union and intersection of the graphs G and H are respectively
View More Questions
Top AP PGECET Questions
- The entropy of single crystalline Silicon at absolute zero will be:
- AP PGECET - 2025
- Thermodynamics
- The minimum amount of work required to operate a refrigerator which removes 1000 Cal heat at $0^\circ$C and rejects at $50^\circ$C will be:
- AP PGECET - 2025
- Thermodynamics
- 1 mole of Argon gas is heated at constant pressure from 200 K to 600 K.
If \( C_p = 4\ \text{cal} \cdot \text{deg}^{-1} \cdot \text{mol}^{-1} \), then the change in entropy will be:
(Given \( \ln 3 = 1.09 \))
- AP PGECET - 2025
- Thermodynamics
- If the vapour pressure at two temperatures of a solid phase in equilibrium with its liquid phase is known, then the latent heat of fusion can be calculated by the:
- AP PGECET - 2025
- Thermodynamics
- The absolute humidity of air at 101.325 kPa is measured to be 0.02 kg of water per kg of dry air. Then the partial pressure of water vapour in the air is:
- AP PGECET - 2025
- Thermodynamics
View More Questions