fg @® @ oonro7Mminsssec G)+ In graph theory, what is the time complexity of finding the...
Fujitsu technical mcq question, verified with a worked answer. Free to practise - no sign-up.
fg @® @ oonro7Mminsssec G)+ In graph theory, what is the time complexity of finding the shortest path between two nodes ina O oO(v) weighted graph using Dijkstra's algorithm? - A) o(va2) - B) O(E + Vlog Vv) - C) O(VA2 log v)
Show answer & explanation
Dijkstra's algorithm, when implemented with a Fibonacci heap, achieves a time complexity of O(E + V log V), where E is the number of edges and V is the number of vertices. This is the most efficient known bound for the algorithm on general weighted graphs.
Step-by-step Derivation:
Step 1: Analyze the operations of Dijkstra's algorithm. The algorithm performs V 'extract-min' operations and at most E 'decrease-key' operations.
Step 2: Evaluate the cost of these operations using a Fibonacci heap. An 'extract-min' operation takes O(log V) amortized time, and a 'decrease-key' operation takes O(1) amortized time.
Step 3: Sum the total costs: Total Time = V * O(log V) + E * O(1) = O(E + V log V).
Step 4: Match this result to the provided options. Option B, despite the typographical noise ('Vlog Vv'), represents the standard O(E + V log V) complexity.