When Depth-First Search Gets It Wrong: Shortest Path Problem Analysis

Anni HuangAnni Huang
9 min read

Table of contents

While working on a recent graph traversal problem, I made an assumption that would prove costly: that Depth-First Search (DFS) and Breadth-First Search (BFS) are interchangeable algorithms. This misconception led me down a rabbit hole of debugging before I realized the fundamental issue—DFS simply cannot guarantee the shortest path in unweighted graphs.

This discovery prompted me to conduct a comprehensive research into when BFS and DFS are truly interchangeable versus when they serve distinct purposes.

In this article, I'll demonstrate specific test cases where DFS fails to find the shortest path, illustrating why BFS is the correct choice for shortest path problems in unweighted graphs.

Code example(Java)

import java.util.*;

class Station {
    String name;
    List<Station> neighbors;

    Station(String name) {
        this.name = name;
        this.neighbors = new ArrayList<>();
    }

    public void addNeighbor(Station neighbor) {
        this.neighbors.add(neighbor);
        neighbor.neighbors.add(this);
    }
}

class MetroBFS {
    public int shortestPath(Station start, Station end) {
        if (start == end) return 0;

        Queue<Station> queue = new LinkedList<>();
        Set<Station> visited = new HashSet<>();
        Map<Station, Integer> distance = new HashMap<>();

        queue.offer(start);
        visited.add(start);
        distance.put(start, 0);

        while (!queue.isEmpty()) {
            Station current = queue.poll();

            for (Station neighbor : current.neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    distance.put(neighbor, distance.get(current) + 1);
                    queue.offer(neighbor);

                    if (neighbor == end) {
                        return distance.get(neighbor);
                    }
                }
            }
        }
        return -1;
    }
}

class MetroDFS {
    public int dfsFirstPath(Station start, Station end) {
        Set<Station> visited = new HashSet<>();
        List<Integer> pathLengths = new ArrayList<>();
        dfsHelper(start, end, visited, 0, pathLengths);
        return pathLengths.isEmpty() ? -1 : pathLengths.get(0); // Return FIRST path found
    }

    private void dfsHelper(Station current, Station target, Set<Station> visited, 
                          int currentLength, List<Integer> pathLengths) {
        if (current == target) {
            pathLengths.add(currentLength);
            return; // Return immediately after finding first path
        }

        visited.add(current);

        for (Station neighbor : current.neighbors) {
            if (!visited.contains(neighbor)) {
                dfsHelper(neighbor, target, visited, currentLength + 1, pathLengths);
                if (!pathLengths.isEmpty()) return; // Stop after first path
            }
        }

        visited.remove(current);
    }
}

public class Main {
    public static void main(String[] args) {
        testCase1_CentralSingaporeNetwork();
        testCase2_LongDetourFirst();
        testCase3_EastWestNetwork();
        testCase4_ComplexInterchangeNetwork();
    }

    // Test Case 1: Central Singapore MRT Network
    public static void testCase1_CentralSingaporeNetwork() {
        System.out.println("=== Test Case 1: Central Singapore MRT Network ===");

        /*
        Network (North-South and East-West lines intersection):
        Orchard ---- Somerset ---- Dhoby Ghaut
            |           |              |
        Raffles Place ---- City Hall ---- Bugis
            |           |              |
        Marina Bay ---- Marina South Pier ---- Esplanade

        Orchard to Esplanade has multiple paths
        */

        Station orchard = new Station("Orchard");
        Station somerset = new Station("Somerset");
        Station dhobyGhaut = new Station("Dhoby Ghaut");
        Station rafflesPlace = new Station("Raffles Place");
        Station cityHall = new Station("City Hall");
        Station bugis = new Station("Bugis");
        Station marinaBay = new Station("Marina Bay");
        Station marinaSouthPier = new Station("Marina South Pier");
        Station esplanade = new Station("Esplanade");

        // Create grid connections (typical MRT interchange pattern)
        orchard.addNeighbor(somerset); somerset.addNeighbor(dhobyGhaut);
        orchard.addNeighbor(rafflesPlace); somerset.addNeighbor(cityHall); dhobyGhaut.addNeighbor(bugis);
        rafflesPlace.addNeighbor(cityHall); cityHall.addNeighbor(bugis);
        rafflesPlace.addNeighbor(marinaBay); cityHall.addNeighbor(marinaSouthPier); bugis.addNeighbor(esplanade);
        marinaBay.addNeighbor(marinaSouthPier); marinaSouthPier.addNeighbor(esplanade);

        MetroBFS bfs = new MetroBFS();
        MetroDFS dfs = new MetroDFS();

        int bfsResult = bfs.shortestPath(orchard, esplanade);
        int dfsResult = dfs.dfsFirstPath(orchard, esplanade);

        System.out.println("BFS Orchard→Esplanade: " + bfsResult + " stations (guaranteed shortest)");
        System.out.println("DFS Orchard→Esplanade: " + dfsResult + " stations (first path found)");
        System.out.println("DFS found optimal path: " + (bfsResult == dfsResult));
        System.out.println();
    }

    // Test Case 2: Long detour through Singapore
    public static void testCase2_LongDetourFirst() {
        System.out.println("=== Test Case 2: Long Detour Through Singapore ===");

        /*
        Network (designed so DFS explores long path first):

        Jurong East ---- Clementi ---- Dover ---- Buona Vista ---- Commonwealth ---- Queenstown ---- Redhill ---- Tiong Bahru ---- Outram Park
            |                                                                                                                                    |
            +------------- Direct Connection (Circle Line) -----------------------------------------------------------------------------+

        Jurong East to Outram Park:
        - Direct: Jurong East → Outram Park (1 step via Circle Line)
        - Long: Jurong East → ... → Tiong Bahru → Outram Park (8 steps via East-West Line)
        */

        Station jurongEast = new Station("Jurong East");
        Station outramPark = new Station("Outram Park");
        Station clementi = new Station("Clementi");
        Station dover = new Station("Dover");
        Station buonaVista = new Station("Buona Vista");
        Station commonwealth = new Station("Commonwealth");
        Station queenstown = new Station("Queenstown");
        Station redhill = new Station("Redhill");
        Station tiongBahru = new Station("Tiong Bahru");

        // Create long East-West line path first (DFS will explore this first)
        jurongEast.addNeighbor(clementi);
        clementi.addNeighbor(dover);
        dover.addNeighbor(buonaVista);
        buonaVista.addNeighbor(commonwealth);
        commonwealth.addNeighbor(queenstown);
        queenstown.addNeighbor(redhill);
        redhill.addNeighbor(tiongBahru);
        tiongBahru.addNeighbor(outramPark);

        // Add direct Circle Line connection last
        jurongEast.addNeighbor(outramPark);

        MetroBFS bfs = new MetroBFS();
        MetroDFS dfs = new MetroDFS();

        int bfsResult = bfs.shortestPath(jurongEast, outramPark);
        int dfsResult = dfs.dfsFirstPath(jurongEast, outramPark);

        System.out.println("BFS Jurong East→Outram Park: " + bfsResult + " stations");
        System.out.println("DFS Jurong East→Outram Park: " + dfsResult + " stations");
        System.out.println("DFS found optimal path: " + (bfsResult == dfsResult));
        System.out.println();
    }

    // Test Case 3: East-West Singapore Network
    public static void testCase3_EastWestNetwork() {
        System.out.println("=== Test Case 3: East-West Singapore Network ===");

        /*
        Network (East-West Line with North-South connections):
        Pasir Ris ---- Tampines ---- Simei ---- Tanah Merah
            |             |           |            |
        Expo ---- Changi Airport ---- Bedok ---- Kembangan
            |             |           |            |
        Marina Bay ---- Bayfront ---- Downtown ---- Telok Ayer
            |             |           |            |
        Raffles Place ---- City Hall ---- Dhoby Ghaut ---- Somerset

        Pasir Ris to Somerset has multiple paths of different lengths
        */

        Station pasirRis = new Station("Pasir Ris"), tampines = new Station("Tampines"), 
                simei = new Station("Simei"), tanahMerah = new Station("Tanah Merah");
        Station expo = new Station("Expo"), changiAirport = new Station("Changi Airport"), 
                bedok = new Station("Bedok"), kembangan = new Station("Kembangan");
        Station marinaBay = new Station("Marina Bay"), bayfront = new Station("Bayfront"), 
                downtown = new Station("Downtown"), telokAyer = new Station("Telok Ayer");
        Station rafflesPlace = new Station("Raffles Place"), cityHall = new Station("City Hall"), 
                dhobyGhaut = new Station("Dhoby Ghaut"), somerset = new Station("Somerset");

        // Row connections (East-West)
        pasirRis.addNeighbor(tampines); tampines.addNeighbor(simei); simei.addNeighbor(tanahMerah);
        expo.addNeighbor(changiAirport); changiAirport.addNeighbor(bedok); bedok.addNeighbor(kembangan);
        marinaBay.addNeighbor(bayfront); bayfront.addNeighbor(downtown); downtown.addNeighbor(telokAyer);
        rafflesPlace.addNeighbor(cityHall); cityHall.addNeighbor(dhobyGhaut); dhobyGhaut.addNeighbor(somerset);

        // Column connections (North-South)
        pasirRis.addNeighbor(expo); expo.addNeighbor(marinaBay); marinaBay.addNeighbor(rafflesPlace);
        tampines.addNeighbor(changiAirport); changiAirport.addNeighbor(bayfront); bayfront.addNeighbor(cityHall);
        simei.addNeighbor(bedok); bedok.addNeighbor(downtown); downtown.addNeighbor(dhobyGhaut);
        tanahMerah.addNeighbor(kembangan); kembangan.addNeighbor(telokAyer); telokAyer.addNeighbor(somerset);

        MetroBFS bfs = new MetroBFS();
        MetroDFS dfs = new MetroDFS();

        int bfsResult = bfs.shortestPath(pasirRis, somerset);
        int dfsResult = dfs.dfsFirstPath(pasirRis, somerset);

        System.out.println("BFS Pasir Ris→Somerset: " + bfsResult + " stations");
        System.out.println("DFS Pasir Ris→Somerset: " + dfsResult + " stations");
        System.out.println("DFS found optimal path: " + (bfsResult == dfsResult));
        System.out.println();
    }

    // Test Case 4: Complex Interchange Network
    public static void testCase4_ComplexInterchangeNetwork() {
        System.out.println("=== Test Case 4: Complex Singapore Interchange Network ===");

        /*
        Realistic Singapore MRT grid covering major interchanges:
        Woodlands ---- Admiralty ---- Sembawang ---- Yishun ---- Khatib
            |             |             |             |           |
        Kranji ---- Marsiling ---- Woodlands North ---- Yio Chu Kang ---- Ang Mo Kio
            |             |             |             |           |
        Tuas Link ---- Tuas West Road ---- Tuas Crescent ---- Boon Lay ---- Pioneer
            |             |             |             |           |
        Gul Circle ---- Tukang ---- Joo Koon ---- Lakeside ---- Chinese Garden
            |             |             |             |           |
        Jurong East ---- Clementi ---- Dover ---- Buona Vista ---- Commonwealth

        Path from Woodlands to Commonwealth:
        - Multiple possible routes with different lengths
        */

        Station[] grid = new Station[26]; // Create a grid of stations
        String[] stationNames = {
            "", // 0-indexed placeholder
            "Woodlands", "Admiralty", "Sembawang", "Yishun", "Khatib",
            "Kranji", "Marsiling", "Woodlands North", "Yio Chu Kang", "Ang Mo Kio", 
            "Tuas Link", "Tuas West Road", "Tuas Crescent", "Boon Lay", "Pioneer",
            "Gul Circle", "Tukang", "Joo Koon", "Lakeside", "Chinese Garden",
            "Jurong East", "Clementi", "Dover", "Buona Vista", "Commonwealth"
        };

        for (int i = 1; i <= 25; i++) {
            grid[i] = new Station(stationNames[i]);
        }

        // Create grid connections (5x5 grid)
        for (int i = 1; i <= 25; i++) {
            int row = (i - 1) / 5;
            int col = (i - 1) % 5;

            // Right connection
            if (col < 4) {
                grid[i].addNeighbor(grid[i + 1]);
            }

            // Down connection  
            if (row < 4) {
                grid[i].addNeighbor(grid[i + 5]);
            }
        }

        MetroBFS bfs = new MetroBFS();
        MetroDFS dfs = new MetroDFS();

        int bfsResult = bfs.shortestPath(grid[1], grid[25]); // Woodlands to Commonwealth
        int dfsResult = dfs.dfsFirstPath(grid[1], grid[25]);

        System.out.println("BFS Woodlands→Commonwealth: " + bfsResult + " stations");
        System.out.println("DFS Woodlands→Commonwealth: " + dfsResult + " stations");
        System.out.println("DFS found optimal path: " + (bfsResult == dfsResult));
        System.out.println();
    }
}

Expected Output

This demonstrates how DFS might suggest taking 8 stops via the East-West Line when there's a direct 1-stop connection via Circle Line - exactly the kind of suboptimal routing that would frustrate real commuters!

=== Test Case 2: Long Detour Through Singapore ===
BFS Jurong East→Outram Park: 1 stations
DFS Jurong East→Outram Park: 8 stations  
DFS found optimal path: false

Great question! Let me explain exactly why DFS fails to find the optimal path in these Singapore MRT examples by analyzing the algorithm's behavior step-by-step.

Core Problem: DFS Explores Depth-First, Not Distance-First

Example Analysis: Jurong East → Outram Park

Let's trace through Test Case 2 where DFS fails dramatically:

Network:
Jurong East ---- Clementi ---- Dover ---- Buona Vista ---- Commonwealth ---- Queenstown ---- Redhill ---- Tiong Bahru ---- Outram Park
    |                                                                                                                                    |
    +------------- Direct Connection (Circle Line) -----------------------------------------------------------------------------+

Available Paths:

  • Optimal: Jurong East → Outram Park (1 step)
  • Suboptimal: Jurong East → Clementi → Dover → ... → Tiong Bahru → Outram Park (8 steps)

Step-by-Step DFS Execution:

// DFS starts at Jurong East
// neighbors = [Clementi, Outram Park] (in order they were added)

1. DFS(Jurong East, visited={})
   - Check neighbors in order: Clementi first, then Outram Park
   - Choose Clementi (first neighbor)

2. DFS(Clementi, visited={Jurong East})
   - Only unvisited neighbor: Dover
   - Choose Dover

3. DFS(Dover, visited={Jurong East, Clementi})
   - Only unvisited neighbor: Buona Vista
   - Choose Buona Vista

4. Continue this pattern...
   Dover → Buona Vista → Commonwealth → Queenstown → Redhill → Tiong Bahru

5. DFS(Tiong Bahru, visited={Jurong East, Clementi, Dover, ...})
   - Only unvisited neighbor: Outram Park
   - TARGET FOUND! Return path length = 8

6. DFS returns 8 (first path found)
   - Never explores the direct Jurong East → Outram Park connection

Why This Happens: Three Key Factors

1. Order of Neighbor Addition

// This order determines DFS exploration sequence
jurongEast.addNeighbor(clementi);    // Added first - DFS explores this first
// ... (long chain of connections)
jurongEast.addNeighbor(outramPark);  // Added last - DFS might never reach this

2. Depth-First Exploration Strategy

  • DFS commits to exploring one path completely before trying alternatives
  • Once it starts down the Clementi path, it must reach a dead end or target before backtracking
  • It doesn't consider "How many steps am I taking?"

3. First-Found Termination

if (current == target) {
    pathLengths.add(currentLength);
    return; // ← Stops immediately after finding ANY path
}

Contrast: Why BFS Succeeds

BFS Execution for Same Network:

// BFS explores by distance levels
Level 0: [Jurong East]
Level 1: [Clementi, Outram Park]  ← Target found at level 1!
// BFS stops here, returns distance = 1

Key Difference: BFS explores all stations at distance 1 before exploring any stations at distance 2.

Visual Comparison

DFS Path Discovery:
Jurong East → Clementi → Dover → Buona Vista → Commonwealth → Queenstown → Redhill → Tiong Bahru → Outram Park
Step:   0  →    1     →   2   →      3       →       4      →      5     →    6   →       7      →       8
        ↑                                                                                                  ↑
      Start                                                                                            Found! (8 steps)

BFS Path Discovery:
Level 0: [Jurong East]
Level 1: [Clementi, Outram Park] ← Found! (1 step)

Real-World Analogy

Imagine you're giving directions to a tourist:

DFS Approach: "Take the first path you see and follow it completely, no matter how long it gets"

  • Tourist follows East-West Line for 8 stops 🤦‍♂️

BFS Approach: "Check all your immediate options first, then consider longer routes"

  • Tourist finds direct Circle Line connection immediately ✅

The Fundamental Issue

DFS optimizes for exploration completeness, not path efficiency. It's designed to:

  • Visit every reachable node
  • Find cycles
  • Perform topological sorting
  • Explore deep hierarchies

But shortest path problems require distance-aware algorithms like BFS, which guarantees that when you first reach a target, you've taken the minimum number of steps.

This is why BFS is the gold standard for shortest path in unweighted graphs - it's mathematically guaranteed to find the optimal solution, while DFS just finds a solution (which might be terrible).

0
Subscribe to my newsletter

Read articles from Anni Huang directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Breadth-Fist-SearchGraphShortestPathJava

Written by

Anni Huang
Anni Huang

I am Anni HUANG, a software engineer with 3 years of experience in IDE development and Chatbot.