Page 78 - Data Structures Handout_Neat

8.3.3 Applications of BFS and DFS

Both BFS and DFS are foundational algorithms with wide-ranging applications:

• BFS Applications:

o Finding shortest paths in unweighted graphs.

o Level-order traversal in trees.

o Network broadcasting and spreading information.
o Solving puzzles like the minimum moves in chess problems.

• DFS Applications:

o Detecting cycles in graphs.
o Checking graph connectivity.

o Topological sorting in directed acyclic graphs.

o Solving mazes and exploring deep paths.

8.4 Shortest Path Algorithms

One of the most important problems in graph theory is finding the shortest path

between vertices. In real-world applications, this corresponds to tasks such as finding the

quickest route between cities, the least costly way to transmit data across a network, or the
most efficient sequence of operations in a system. The shortest path problem can vary

depending on whether the graph is weighted or unweighted, directed or undirected, and

whether negative edge weights are allowed. Several algorithms have been developed to solve

these problems, each with its own strengths, limitations, and areas of application.

8.4.1 Dijkstra’s Algorithm

Dijkstra’s algorithm is one of the most famous shortest path algorithms. It is designed

for graphs with non-negative edge weights and finds the shortest path from a single source

vertex to all other vertices. The algorithm works by maintaining a set of vertices whose

shortest distance from the source is already known and repeatedly selecting the vertex with
the smallest tentative distance to expand.

The intuition behind Dijkstra’s algorithm is like gradually spreading out from the

source, always choosing the closest unexplored vertex. This ensures that once a vertex’s

78