In graph theory, which algorithm is used to find the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights?
Answer and explanation
Correct answer: B. Dijkstra's algorithm
- Step 1: Identify the problem requirement: single-source shortest path with non-negative edge weights.
- Step 2: Dijkstra's algorithm uses a min-priority queue to greedily expand the shortest tentative distance from the source, solving in time.
Answer
Dijkstra's algorithm.
Why not the others: Kruskal's finds minimum spanning trees; Floyd-Warshall finds all-pairs shortest paths in ; DFS explores graphs without finding weighted shortest paths.
Practise more Algorithms and Python Programming.
Free questions with an explanation for every one, and full timed EmSAT Achieve (UAE) mock tests.
More Algorithms and Python Programming questions
- What is the output of the following Python expression: [x**2 for x in range(6) if x % 2 != 0]?
- What is the worst-case time complexity of searching for an element in a balanced binary search tree (AVL tree) containing n nodes?
- What will be printed by the following Python code snippet?
def func(val, lst=[]):
lst.append(val)
return lst
print(func(1))
print(… - Which abstract data structure operates on a First-In, First-Out (FIFO) ordering principle?
- What is the return value of executing the recursive Python function `mystery(4)`?
def mystery(n):
if n <= 1:
return 1
retur… - What is the worst-case time complexity of the standard QuickSort algorithm when the chosen pivot is consistently the smallest or largest ele…