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

Chapter 3: Dijkstra’s Algorithm in Java

Dijkstra’s Algorithm is a single-source shortest path algorithm used to find the shortest path from a starting node to all other nodes in a graph with non-negative edge weights. It works on both directed and undirected graphs and is commonly applied in navigation systems, network routing, and resource optimization.

The core idea of Dijkstra's algorithm is to maintain a priority queue (min-heap) where the node with the minimum tentative distance is always picked next. It uses a greedy approach, updating the shortest known distance to each vertex and relaxing edges until the shortest path to all nodes is determined.

The algorithm works best when implemented using adjacency lists and a priority queue, especially for sparse graphs. It does not work correctly if the graph contains negative edge weights.

2. Dijkstra’s Algorithm Code (2 Examples)

a. Syllabus-Oriented Example (Shortest Path in Weighted Graph)

import java.util.*;

public class DijkstraExample {

    static class Node implements Comparable<Node> {

        int vertex, weight;

        Node(int v, int w) {

            this.vertex = v;

            this.weight = w;

        }

        public int compareTo(Node other) {

            return this.weight - other.weight;

        }

    }

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

        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 current = pq.poll();

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

                int newDist = dist[current.vertex] + neighbor.weight;

                if (newDist < dist[neighbor.vertex]) {

                    dist[neighbor.vertex] = newDist;

                    pq.add(new Node(neighbor.vertex, newDist));

                }

            }

        }

        System.out.println("Shortest distances from node " + source + ": " + Arrays.toString(dist));

    }

    public static void main(String[] args) {

        int V = 5;

        List<List<Node>> graph = new ArrayList<>();

        for (int i = 0; i < V; i++) graph.add(new ArrayList<>());

        graph.get(0).add(new Node(1, 10));

        graph.get(0).add(new Node(2, 3));

        graph.get(1).add(new Node(2, 1));

        graph.get(2).add(new Node(1, 4));

        graph.get(2).add(new Node(3, 2));

        graph.get(3).add(new Node(4, 7));

        graph.get(4).add(new Node(3, 9));

        dijkstra(V, graph, 0);

    }

}

b. Real-World Example (GPS Navigation - Shortest Route)

// Simplified example for GPS-style routing using Dijkstra

// Nodes represent cities, and edge weights represent distance in kilometers

Map<String, List<Node>> buildCityMap() {

    Map<String, List<Node>> map = new HashMap<>();

    map.put("A", Arrays.asList(new Node("B", 5), new Node("C", 10)));

    map.put("B", Arrays.asList(new Node("C", 2), new Node("D", 3)));

    map.put("C", Arrays.asList(new Node("D", 1)));

    map.put("D", new ArrayList<>());

    return map;

}

class Node {

    String city;

    int distance;

    Node(String city, int distance) {

        this.city = city;

        this.distance = distance;

    }

}

// Due to complexity, full real-world Dijkstra for strings would involve a mapping and adjusted implementation.

(Note: Real-world applications typically involve more advanced data structures like HashMap<String, List<Node>> for string-based graph representations.)

3. Pros of Dijkstra’s Algorithm

• ✅ Efficient for non-negative weighted graphs.
• ✅ Always finds the optimal shortest path.
• ✅ Suitable for both directed and undirected graphs.
• ✅ Can be easily implemented using priority queues (min-heaps).
• ✅ Scales well with sparse graphs using adjacency lists.

4. Cons of Dijkstra’s Algorithm

• ❌ Does not work with negative edge weights.
• ❌ Less efficient on dense graphs without heap optimization.
• ❌ Requires more complex data structures (e.g., heaps, adjacency lists).
• ❌ Slower than BFS for unweighted graphs.
• ❌ Harder to debug compared to BFS/DFS due to edge relaxations.

5. How Dijkstra’s Is Better Than Other Algorithms

• Compared to BFS: Handles weighted graphs, finds optimal shortest path.
• Compared to DFS: DFS doesn’t guarantee shortest path; Dijkstra does.
• Compared to Bellman-Ford: Dijkstra is much faster (O((V + E) log V) vs O(V × E)) for graphs without negative weights.
• Compared to Floyd-Warshall: More efficient for single-source shortest paths.

6. Best-Case Scenarios to Use Dijkstra’s Algorithm

• Navigation systems like Google Maps or GPS apps.
• Network routing protocols (e.g., OSPF).
• Game development for AI movement.
• Resource management systems (e.g., shortest job allocation).
• Single-source shortest path in real-world logistics networks.

7. Applications of Dijkstra’s Algorithm

• Road networks & GPS routing.
• Network packet routing (e.g., Cisco OSPF).
• Project planning to calculate minimum time paths.
• Robot pathfinding in grid-based environments.
• Telecommunication networks for signal optimization.

8. Worst-Case Scenarios to Use Dijkstra’s Algorithm

• Graphs with negative edge weights — results will be incorrect.
• Dense graphs with many edges — can be inefficient without optimization.
• When real-time responsiveness is needed and the graph is massive.
• All-pairs shortest paths — better handled by Floyd-Warshall.
• Situations requiring cycle detection or graph structure analysis — use DFS instead.