Question:
Which algorithm is specifically designed to solve the Single-Source Shortest Path problem in a graph containing negative edge weights (and detect negative cycles)?
नकारात्मक किनारे भार वाले ग्राफ में सिंगल-सोर्स शॉर्टेस्ट पाथ खोजने और नकारात्मक चक्रों का पता लगाने के लिए कौन सा एल्गोरिदम डिज़ाइन किया गया है?
Options:
- Bellman-Ford Algorithm
- Dijkstra’s Algorithm
- Prim’s Algorithm
- Kruskal’s Algorithm
- बेलमैन-फोर्ड एल्गोरिदम (Bellman-Ford)
- डिजक्स्ट्रा एल्गोरिदम
- प्रिम्स एल्गोरिदम
- क्रुस्कल एल्गोरिदम
Correct Answer: a)
Explanation:
The Bellman-Ford algorithm relaxes all \(E\) edges \(V-1\) times in \(O(V \cdot E)\) time. A \(V\)-th iteration that successfully relaxes any edge proves the existence of a negative weight cycle reachable from the source.
बेलमैन-फोर्ड एल्गोरिदम \(O(V \cdot E)\) समय में नकारात्मक भार वाले किनारों को संभालता है और \(V\)-वें रिलैक्सेशन पर नकारात्मक चक्र का पता लगाता है।