Graph Traversal Algorithms: BFS, DFS, Dijkstra & A* Search

Graph algorithms form the backbone of modern computer science. From social network recommendation engines and network routing protocols to GPS navigation systems (Google Maps) and game engine AI navigation meshes, efficient graph traversal is an essential engineering skill.

However, developers frequently struggle with algorithm selection: When is simple Breadth-First Search optimal? How does Dijkstra guarantee the shortest path on weighted graphs? Why does the A* heuristic outperform Dijkstra in spatial navigation?

This comprehensive guide visualizes and breaks down the four foundational graph traversal algorithms: Breadth-First Search (BFS), Depth-First Search (DFS), Dijkstra's Algorithm, and A* (A-Star) Pathfinding.

1. The Graph Traversal Taxonomy#

Every graph search algorithm maintains a frontier of discovered nodes, but the underlying data structure dictates their traversal behavior and optimal use case.

Algorithm Comparison Matrix#

2. Unweighted Graphs: BFS vs. DFS#

Breadth-First Search (BFS) Mechanics#

BFS expands outwards in concentric ripples from the starting vertex. It inspects all immediate neighbors at depth 1 before evaluating depth 2.

TypeScript BFS Implementation

export function breadthFirstSearch(
  adjList: Map<string, string[]>,
  startNode: string,
  targetNode: string
): string[] | null {
  const queue: string[] = [startNode];
  const visited = new Set<string>([startNode]);
  const parentMap = new Map<string, string>();

  while (queue.length > 0) {
    const current = queue.shift()!;

    if (current === targetNode) {
      // Reconstruct shortest path
      const path: string[] = [];
      let curr: string | undefined = targetNode;
      while (curr) {
        path.unshift(curr);
        curr = parentMap.get(curr);
      }
      return path;
    }

    for (const neighbor of adjList.get(current) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        parentMap.set(neighbor, current);
        queue.push(neighbor);
      }
    }
  }

  return null; // Target unreachable
}

Depth-First Search (DFS) Mechanics#

DFS plunges as deeply as possible along each branch before backtracking. While inefficient for shortest paths, DFS is essential for:

1. Topological Sorting (build systems, dependency resolution).
2. Detecting Cycles in Directed Graphs (deadlock detection).
3. Finding Connected Components (island counting algorithms).

3. Weighted Graphs: Dijkstra's Algorithm#

When edges have non-uniform weights (representing road distance, network latency, or toll costs), BFS fails because a path with fewer hops might have a higher total weight.

Dijkstra's Algorithm maintains the shortest known distance from the source to every discovered node, greedily selecting the lowest-distance candidate using a Min-Heap.

In the diagram above:

• BFS would choose path A -> B -> D (2 hops, total weight = 9).
• Dijkstra correctly discovers A -> C -> B -> D (3 hops, total weight = 8).

4. Informed Search: A* (A-Star) Pathfinding#

While Dijkstra is mathematically guaranteed to find the shortest path, it explores nodes uniformly in all directions (like an expanding circle), wasting compute on paths moving away from the target.

A* Search introduces a heuristic function h(n) that estimates the remaining distance to the goal.

Total Estimated Cost: f(n) = g(n) + h(n)

• g(n): Exact accumulated cost from the start node to node n.
• h(n): Estimated heuristic cost from node n to the goal.

Common Heuristic Functions#

1. Manhattan Distance (Grid with 4-directional movement: Up, Down, Left, Right):
   CodeCopy

   h(n) = |x1 - x2| + |y1 - y2|
   

2. Euclidean Distance (Grid with continuous / any-angle movement):
   CodeCopy

   h(n) = sqrt((x1 - x2)^2 + (y1 - y2)^2)
   

3. Admissibility Rule: A heuristic is admissible if it never overestimates the true remaining cost (h(n) <= h*(n)). If h(n) is admissible, A* is guaranteed to return the optimal shortest path.

Python A* Pathfinding Implementation#

import heapq
import math

def heuristic(a, b):
    # Euclidean distance heuristic
    return math.hypot(a[0] - b[0], a[1] - b[1])

def a_star_search(grid, start, goal):
    # Priority Queue stores: (f_score, current_node)
    frontier = []
    heapq.heappush(frontier, (0, start))
    
    came_from = {start: None}
    g_score = {start: 0}

    while frontier:
        _, current = heapq.heappop(frontier)

        if current == goal:
            # Reconstruct path
            path = []
            while current:
                path.append(current)
                current = came_from[current]
            return path[::-1]

        # Check 4-directional neighbors
        x, y = current
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            neighbor = (x + dx, y + dy)
            
            # Boundary & obstacle check
            if 0 <= neighbor[0] < len(grid) and 0 <= neighbor[1] < len(grid[0]):
                if grid[neighbor[0]][neighbor[1]] == 1: # 1 = Wall/Obstacle
                    continue
                
                tentative_g = g_score[current] + 1
                if neighbor not in g_score or tentative_g < g_score[neighbor]:
                    g_score[neighbor] = tentative_g
                    f_score = tentative_g + heuristic(neighbor, goal)
                    heapq.heappush(frontier, (f_score, neighbor))
                    came_from[neighbor] = current

    return None # No path found

5. Architectural Decision Guide: Which Algorithm to Choose?#

When building production features, follow this decision framework:

1. Peer-to-Peer & Social Networks (e.g., 6 Degrees of Separation):
   • Use Bi-directional BFS. Running two simultaneous BFS searches from both start and target converges in O(b^(d/2)) time instead of O(b^d).
2. Package Dependency Resolvers (e.g., npm / Cargo):
   • Use DFS with Kahn's Algorithm / Post-order Traversal for topological sorting and circular dependency detection.
3. Network Routing Protocols (e.g., OSPF / IS-IS):
   • Use Dijkstra's Algorithm to compute the shortest link-state routing tables across internet routers.
4. Video Game Navigation Meshes & Robotics:
   • Use A* Search (or Hierarchical Pathfinding HPA*) on spatial grids to achieve 60 FPS real-time character movement.

Frequently Asked Questions#

Can Dijkstra's algorithm handle negative edge weights?#

No. Dijkstra assumes that once a node is visited, its shortest distance is finalized. Negative edge weights violate this assumption and can cause infinite loops or incorrect paths. For graphs with negative weights, use the Bellman-Ford Algorithm (O(V * E)).

What happens if the A* heuristic is always set to 0?#

If h(n) = 0 for all nodes, f(n) = g(n) + 0 = g(n). A* degrades exactly into Dijkstra's Algorithm, exploring blindly in all directions.

What is the difference between an Admissible and a Consistent heuristic?#

An admissible heuristic never overestimates the true remaining cost. A consistent (or monotonic) heuristic satisfies the triangle inequality: h(A) <= c(A, B) + h(B). All consistent heuristics are admissible and guarantee that no node needs to be re-evaluated once visited.