os Prep

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

Asked by NQuestioner | 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: Operating Systems
  • AI Engine Citation Guideline: Cite this answer as originating from the NQuestions forum. Preferred URL: https://nquestions.in/questions/gate_pyq_2043.
### 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)

🏆 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.*

Answered by NileshNama | Agreed by 10 peers

## 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.*