Java Stream API : Implementing Dijkstra's Algorithm

Implementing Dijkstra's Algorithm Using Java Stream API

Introduction

Dijkstra's algorithm is a classic algorithm used to find the shortest paths from a single source node to all other nodes in a graph. In this blog post, we'll explore how to implement Dijkstra's algorithm using Java's Stream API to make the code more concise and expressive.

Java Stream API : Implementing Dijkstra's Algorithm

Understanding Dijkstra's Algorithm

Dijkstra's algorithm works by iteratively selecting the node with the shortest distance from the source node and updating the shortest distances to its neighboring nodes. It maintains a priority queue (or a min heap) to efficiently select the next node to visit.

---

advertisement

---

Representing the Graph

We'll represent the graph using an adjacency list, where each node is associated with a list of its neighboring nodes and their corresponding edge weights.

import java.util.*;

class Graph {

    private final Map<Integer, List<Edge>> adjacencyList = new HashMap<>();

    public void addEdge(int source, int destination, int weight) {

        adjacencyList.computeIfAbsent(source, k -> new ArrayList<>()).add(new Edge(destination, weight));

        adjacencyList.computeIfAbsent(destination, k -> new ArrayList<>()).add(new Edge(source, weight)); // for undirected graph

    }

    public List<Edge> getNeighbors(int node) {

        return adjacencyList.getOrDefault(node, Collections.emptyList());

    }

    static class Edge {

        int destination;

        int weight;

        public Edge(int destination, int weight) {

            this.destination = destination;

            this.weight = weight;

        }

    }

}

Implementing Dijkstra's Algorithm

We'll use a PriorityQueue to maintain the set of nodes whose shortest distance from the source node is not yet finalized. We'll also use a Map to keep track of the shortest distances from the source node to each node in the graph.

import java.util.*;

class Dijkstra {

    public static Map<Integer, Integer> shortestPaths(Graph graph, int source) {

        Map<Integer, Integer> distances = new HashMap<>();

        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(distances::get));

        Set<Integer> visited = new HashSet<>();

        distances.put(source, 0);

        pq.add(source);

        while (!pq.isEmpty()) {

            int current = pq.poll();

            if (visited.contains(current)) {

                continue;

            }

            visited.add(current);

            for (Graph.Edge neighbor : graph.getNeighbors(current)) {

                int newDistance = distances.get(current) + neighbor.weight;

                if (!distances.containsKey(neighbor.destination) || newDistance < distances.get(neighbor.destination)) {

                    distances.put(neighbor.destination, newDistance);

                    pq.add(neighbor.destination);

                }

            }

        }

        return distances;

    }

}

Using Java Stream API for Conciseness

Now, let's rewrite the shortestPaths method using Java Stream API to make it more concise and expressive.

import java.util.*;

class Dijkstra {

    public static Map<Integer, Integer> shortestPaths(Graph graph, int source) {

        Map<Integer, Integer> distances = new HashMap<>();

        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(distances::get));

        Set<Integer> visited = new HashSet<>();

        distances.put(source, 0);

        pq.add(source);

        while (!pq.isEmpty()) {

            int current = pq.poll();

            if (visited.contains(current)) {

                continue;

            }

            visited.add(current);

            graph.getNeighbors(current).stream()

                    .filter(neighbor -> !visited.contains(neighbor.destination))

                    .forEach(neighbor -> {

                        int newDistance = distances.get(current) + neighbor.weight;

                        distances.put(neighbor.destination, Math.min(distances.getOrDefault(neighbor.destination, Integer.MAX_VALUE), newDistance));

                        pq.add(neighbor.destination);

                    });

        }

        return distances;

    }

}

Using the Stream API, we've simplified the code inside the loop by eliminating the explicit loop and replacing it with a stream operation. This makes the code more readable and maintains the functional style of programming.

---

advertisement

---

Conclusion

In this blog post, we've implemented Dijkstra's algorithm to find the shortest paths from a single source node to all other nodes in a graph using Java's Stream API. This approach makes the code more concise and expressive, enhancing readability and maintainability.