Question:
Which algorithm is used to find the shortest paths between ALL pairs of vertices in a weighted graph with positive or negative edge weights (without negative cycles)?
सकारात्मक या नकारात्मक किनारे भार (बिना नकारात्मक चक्र) वाले भारित ग्राफ में शीर्षों के सभी जोड़ों के बीच सबसे छोटे पथ खोजने के लिए किस कलनविधि का उपयोग किया जाता है?
Options:
- Floyd-Warshall Algorithm
- Dijkstra’s Algorithm
- Prim’s Algorithm
- Kruskal’s Algorithm
- फ़्लॉइड-मार्शल एल्गोरिदम (Floyd-Warshall)
- डिजक्स्ट्रा एल्गोरिदम
- प्रिम्स एल्गोरिदम
- क्रुस्कल एल्गोरिदम
Correct Answer: a)
Explanation:
The Floyd-Warshall algorithm is a dynamic programming algorithm that finds all-pairs shortest paths in \(O(V^3)\) time, handling negative edge weights correctly as long as there are no negative weight cycles.
फ़्लॉइड-मार्शल (Floyd-Warshall) एल्गोरिदम डायनामिक प्रोग्रामिंग का उपयोग करके \(O(V^3)\) समय में सभी शीर्ष जोड़ों के बीच सबसे छोटा पथ ज्ञात करता है।