DevNet Associate (DEVASC) v1.0Software Development and DesignHard
A developer needs to implement an algorithm that efficiently finds the shortest path between two nodes in a network graph. The network graph has weighted edges representing latency between devices. Which algorithm is most suitable for this task?
- ADepth-First Search (DFS)
- BBreadth-First Search (BFS)
- CLinear Search
- DDijkstra's Algorithm
Show answer & explanationAnswer & explanation
Correct answer: D. Dijkstra's Algorithm
Dijkstra's Algorithm is specifically designed to find the shortest paths between nodes in a graph, considering edge weights (like latency). BFS and DFS find paths but do not account for weights, and Linear Search is for finding an item in a list, not pathfinding in a graph.
Why the other options are wrong
- A. DFS explores as far as possible along each branch before backtracking; it does not guarantee the shortest path, weighted or unweighted.
- B. BFS finds the shortest path in terms of the number of edges (unweighted graph), not weighted path length.
- C. Linear Search is an algorithm for finding an item within a list; it is not applicable to pathfinding in a graph.
Dijkstra's Algorithm
Dijkstra's Algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It works for graphs with non-negative edge weights.
- Finds shortest path from a single source to all other nodes
- Works on graphs with non-negative edge weights
- Greedy algorithm approach
- Commonly used in network routing protocols
Memory trick: Dijkstra 'distances' itself from bad paths, always finding the shortest weighted route.