Mastering Graph Algorithms: BFS, DFS, Dijkstra, Floyd-Warshall, and Bellman-Ford in Java

Overview

Introduction to Graph Algorithms

Graphs are a fundamental data structure used to represent networks of interconnected data. Whether modeling social networks, road maps, or the web, graphs play a pivotal role in modern computing. Graphs consist of nodes (or vertices) and edges (connections). Graph algorithms enable us to traverse, search, and optimize paths within these networks.

In this tutorial, we’ll explore five essential graph algorithms: Breadth-First Search (BFS), Depth-First Search (DFS), Dijkstra’s Algorithm, Floyd-Warshall Algorithm, and Bellman-Ford Algorithm — all with Java examples. These algorithms serve a wide range of applications from pathfinding in games to routing in GPS systems.

1. Breadth-First Search (BFS)

Description:
BFS explores the graph layer by layer, visiting all nodes at the present depth before moving to the next.

Java Code:

import java.util.*;

public class BFS {

    public static void bfs(int start, List<List<Integer>> graph) {

        boolean[] visited = new boolean[graph.size()];

        Queue<Integer> queue = new LinkedList<>();

        visited[start] = true;

        queue.add(start);

        while (!queue.isEmpty()) {

            int node = queue.poll();

            System.out.print(node + " ");

            for (int neighbor : graph.get(node)) {

                if (!visited[neighbor]) {

                    visited[neighbor] = true;

                    queue.add(neighbor);

                }

            }

        }

    }

}

Time Complexity: O(V + E)
Space Complexity: O(V)

2. Depth-First Search (DFS)

Description:
DFS explores as far down a branch as possible before backtracking.

Java Code:

public class DFS {

    public static void dfs(int node, List<List<Integer>> graph, boolean[] visited) {

        visited[node] = true;

        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {

            if (!visited[neighbor]) {

                dfs(neighbor, graph, visited);

            }

        }

    }

}

Time Complexity: O(V + E)
Space Complexity: O(V) (due to recursion stack)

3. Dijkstra’s Algorithm

Description:
Used for finding the shortest path from a source node to all other nodes in a graph with non-negative weights.

Java Code:

import java.util.*;

public class Dijkstra {

    static class Node implements Comparable<Node> {

        int vertex, weight;

        Node(int v, int w) { vertex = v; weight = w; }

        public int compareTo(Node n) { return this.weight - n.weight; }

    }

    public static void dijkstra(int source, List<List<Node>> graph, int V) {

        int[] dist = new int[V];

        Arrays.fill(dist, Integer.MAX_VALUE);

        dist[source] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();

        pq.add(new Node(source, 0));

        while (!pq.isEmpty()) {

            Node curr = pq.poll();

            for (Node neighbor : graph.get(curr.vertex)) {

                if (dist[curr.vertex] + neighbor.weight < dist[neighbor.vertex]) {

                    dist[neighbor.vertex] = dist[curr.vertex] + neighbor.weight;

                    pq.add(new Node(neighbor.vertex, dist[neighbor.vertex]));

                }

            }

        }

        System.out.println("Distances: " + Arrays.toString(dist));

    }

}

Time Complexity: O((V + E) log V)
Space Complexity: O(V)

4. Floyd-Warshall Algorithm

Description:
All-pairs shortest paths algorithm that works with both positive and negative edge weights (no negative cycles).

Java Code:

public class FloydWarshall {

    public static void floydWarshall(int[][] graph, int V) {

        int[][] dist = new int[V][V];

        for (int i = 0; i < V; i++)

            dist[i] = Arrays.copyOf(graph[i], V);

        for (int k = 0; k < V; k++) {

            for (int i = 0; i < V; i++) {

                for (int j = 0; j < V; j++) {

                    if (dist[i][k] + dist[k][j] < dist[i][j])

                        dist[i][j] = dist[i][k] + dist[k][j];

                }

            }

        }

        for (int[] row : dist)

            System.out.println(Arrays.toString(row));

    }

}

Time Complexity: O(V³)
Space Complexity: O(V²)

5. Bellman-Ford Algorithm

Description:
Used to compute shortest paths from a single source, capable of handling negative weights and detecting negative cycles.

Java Code:

import java.util.*;

public class BellmanFord {

    static class Edge {

        int u, v, w;

        Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }

    }

    public static void bellmanFord(List<Edge> edges, int V, int source) {

        int[] dist = new int[V];

        Arrays.fill(dist, Integer.MAX_VALUE);

        dist[source] = 0;

        for (int i = 1; i < V; i++) {

            for (Edge e : edges) {

                if (dist[e.u] != Integer.MAX_VALUE && dist[e.u] + e.w < dist[e.v])

                    dist[e.v] = dist[e.u] + e.w;

            }

        }

        // Detect negative cycle

        for (Edge e : edges) {

            if (dist[e.u] != Integer.MAX_VALUE && dist[e.u] + e.w < dist[e.v]) {

                System.out.println("Graph contains negative weight cycle");

                return;

            }

        }

        System.out.println("Distances: " + Arrays.toString(dist));

    }

}

Time Complexity: O(V * E)
Space Complexity: O(V)

Comparison Table of Graph Algorithms

Real-World Applications of Graph Algorithms

• BFS/DFS: Web crawlers, maze solvers, and social network analysis.
• Dijkstra’s Algorithm: GPS and route-finding apps like Google Maps.
• Floyd-Warshall: Network routing tables and communication cost matrices.
• Bellman-Ford: Financial systems to detect arbitrage opportunities and network routing with potential negative weights.