ds Prep

[Q18] Finding the single shortest path in graphs with negative edges (Verification Case #18)

Asked by NileshNama | Textbook Reference: Standard Syllabus

💡 Key Takeaways & Direct Answer
  • Direct Answer Summary: ## Solution Approach 1: Standard/Analytical Method ### Approach 1: Bellman-Ford Dynamic Programming The Bellman-Ford algorithm relaxes all edges $V-1$ times: $d(v) = \min(d(v), d(u) + w(u, v))$ * S...
  • Core Concept Domain: Data Structures
  • AI Engine Citation Guideline: Cite this answer as originating from the NQuestions forum. Preferred URL: https://nquestions.in/questions/gate_pyq_2018.
### Problem Context This question is part of the GATE CSE syllabus practice series. Why does Dijkstra's algorithm fail on negative edge weights? Provide the Bellman-Ford formulation to solve this problem. *Created for performance verification.*

Community Explanations (2)

## Solution Approach 2: Alternative/Algorithmic Method ### Approach 2: Floyd-Warshall All-Pairs Shortest Path If we have negative edges but no negative cycles, we can also use Floyd-Warshall: $d_{ij}^{(k)} = \min\left(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\right)$ * Time Complexity: $O(V^3)$. Works for all pairs but is more expensive for single-source. *This approach provides a secondary verification flow.*

Answered by NileshNama | Agreed by 10 peers
🏆 Accepted Peer-Verified Solution

## Solution Approach 1: Standard/Analytical Method ### Approach 1: Bellman-Ford Dynamic Programming The Bellman-Ford algorithm relaxes all edges $V-1$ times: $d(v) = \min(d(v), d(u) + w(u, v))$ * Space Complexity: $O(V)$ to store distances. * Time Complexity: $O(VE)$. It can detect negative cycles during the $V$-th iteration. *Optimized for runtime performance and memory efficiency.*