Question:
In Dijkstra’s single-source shortest path algorithm implemented with a Min-Heap (Binary Heap), what is the worst-case time complexity for a graph with \(V\) vertices and \(E\) edges?
मिन-हीप (बाइनरी हीप) के साथ कार्यान्वित डिजक्स्ट्रा के एकल-स्रोत सबसे छोटे पथ एल्गोरिदम में \(V\) शीर्षों और \(E\) किनारों वाले ग्राफ के लिए सबसे खराब स्थिति की समय जटिलता क्या है?
Options:
- \(O((V + E) \log V)\)
- \(O(V^2)\)
- \(O(E \log E + V)\)
- \(O(V E)\)
- \(O((V + E) \log V)\)
- \(O(V^2)\)
- \(O(E \log E + V)\)
- \(O(V E)\)
Correct Answer: a)
Explanation:
Each vertex is extracted once (\(V \log V\)) and each edge can trigger a decrease-key operation in the heap (\(E \log V\)), resulting in total time \(O((V + E) \log V)\).
बाइनरी हीप के साथ प्रत्येक शीर्ष को निकालने में \(V \log V\) और किनारों के रिलैक्सेशन में \(E \log V\) समय लगता है, जिससे कुल समय \(O((V + E) \log V)\) होता है।