Graph Traversal and Shortest Path Algorithms

1. Graphs: The Language of Connections

Before we dive into the algorithms, let's quickly review what a graph is. A graph is a data structure consisting of:

• Vertices (or Nodes): The entities or points in the network.
• Edges: The connections between pairs of vertices.

Edges can be undirected (a two-way street) or directed (a one-way street). They can also have weights, which represent a cost, distance, or time to travel between vertices.

For a quick refresher on graph terminology and how they are represented, you can skim the first part of this handy cheat sheet.

2. Graph Traversal: Exploring the Graph

Graph traversal is the process of systematically visiting every vertex in a graph. The two most common methods are Breadth-First Search (BFS) and Depth-First Search (DFS). They explore the graph in fundamentally different ways.

The following video from Abdul Bari provides an excellent, intuitive explanation of both.

Let's summarize the key characteristics of each.

Breadth-First Search (BFS)

• Strategy: Explores "level by level." It visits the starting node, then all nodes one edge away, then all nodes two edges away, and so on.
• Data Structure: Uses a Queue (First-In, First-Out) to manage which node to visit next.
• Key Application: Finds the shortest path between two nodes in an unweighted graph. The "shortest path" here means the path with the fewest number of edges.

Here's a standard pseudocode for BFS, which you can find in the lecture notes from the University of Washington.

Depth-First Search (DFS)

• Strategy: Explores as deeply as possible along one path before backtracking.
• Data Structure: Uses a Stack (Last-In, First-Out), or can be implemented elegantly using recursion (which implicitly uses the call stack).
• Key Applications: Checking if a path exists between two nodes, detecting cycles in a graph, and as a component in other algorithms like topological sorting.

BFS vs. DFS: Quick Comparison

This table summarizes the core differences, which is perfect for your quick-reference notes.

Source: Adapted from "Data Structures and Algorithms Cheat Sheet"

3. Shortest Path in Weighted Graphs: Dijkstra's Algorithm

BFS works perfectly for finding the shortest path when all edges are equal. But what if the edges have weights or costs? A path with more edges might be "shorter" if its total weight is less. This is where Dijkstra's algorithm comes in.

Dijkstra's Algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.

• Strategy: It's a greedy algorithm. It maintains a set of "visited" nodes for which the shortest path is known. At each step, it greedily selects the unvisited node that is closest to the source.
• Core Concept (Relaxation): For the newly visited node, it checks all its unvisited neighbors. If the path to a neighbor through the current node is shorter than any previously found path, it updates the neighbor's distance.

This video provides another excellent walkthrough of the process.

Dijkstra's Algorithm: High-Level Pseudocode

Here is the general idea, which you can also see worked out in detail on slide 35 of the Lecture 17: BFS, DFS, Dijkstra PDF resource.

1. Initialization:

   • Create a distTo map to store the shortest distance from the source to every other node. Set the source's distance to 0 and all others to infinity.
   • Create a priority queue to store vertices to visit, prioritized by their distance. Add the source vertex.
   • Create a set of known (or visited) vertices, initially empty.

2. Iteration:

   • While the priority queue is not empty:
     • Extract the vertex u with the smallest distance from the queue.
     • If u is already known, continue. Add u to the known set.
     • For each neighbor v of u:
       • Perform relaxation: If distTo[u] + weight(u, v) < distTo[v], update distTo[v] and add v to the priority queue with its new, smaller distance.

The process stops when all reachable vertices have been visited.

Conclusion

In this lesson, we covered three fundamental graph algorithms that are essential for problem-solving in AI and computer science.

Key Takeaways:

• BFS (Breadth-First Search): Uses a Queue to explore level-by-level. It is guaranteed to find the shortest path in terms of the number of edges, making it ideal for unweighted graphs.
• DFS (Depth-First Search): Uses a Stack or recursion to explore as far as possible down each branch before backtracking. It is used for path existence, cycle detection, and exploring all possibilities.
• Dijkstra's Algorithm: A greedy algorithm that finds the shortest path from a source to all other nodes in a weighted graph. It requires that all edge weights be non-negative.

Preview of the Next Lesson:
The traversal methods we discussed today, BFS and DFS, are considered uninformed search algorithms because they explore systematically without any extra information about where the goal might be. In our next lesson, we will cover the learning outcome: "Contrast uninformed search with informed search (A) and adversarial search (Minimax)."* You'll see how an "informed" search algorithm like A* uses a heuristic (an educated guess) to guide its search much more efficiently. We will also look at adversarial search for situations like games where you have an opponent working against you.