Java Stream API : Find Shortest Path Between Two Nodes in a Graph

Finding the Shortest Path Between Two Nodes in a Graph Using Java Stream API

Introduction

Graphs are fundamental data structures used in computer science to model relationships between objects. One common problem in graph theory is finding the shortest path between two nodes. In this blog post, we will explore how to solve this problem using the Java Stream API.

Java Stream API : Find Shortest Path Between Two Nodes in a Graph

Understanding the Problem

Before we dive into the solution, let's understand the problem statement. Given a graph represented as a collection of nodes and edges, we need to find the shortest path between two given nodes. The path should minimize the sum of the weights of its edges.

Representing the Graph

To represent a graph in Java, we can use a Map where the keys represent nodes and the values represent the edges of each node. Each edge can be represented as a pair of nodes (destination, weight). Here's a simple implementation:

import java.util.*;

public class Graph {
private Map<Integer, List<Edge>> adjacencyList;

public Graph() {
this.adjacencyList = new HashMap<>();
}

public void addNode(int node) {
adjacencyList.putIfAbsent(node, new ArrayList<>());
}

public void addEdge(int source, int destination, int weight) {
adjacencyList.get(source).add(new Edge(destination, weight));
}

public List<Edge> getEdges(int node) {
return adjacencyList.get(node);
}

public static class Edge {
private int destination;
private int weight;

public Edge(int destination, int weight) {
this.destination = destination;
this.weight = weight;
}

public int getDestination() {
return destination;
}

public int getWeight() {
return weight;
}
}
}

Finding the Shortest Path Using Java Stream API

To find the shortest path between two nodes in a graph, we can use Dijkstra's algorithm. Here's a high-level overview of the algorithm:

1. Initialize a distance array to store the shortest distance from the source node to each node in the graph. Initialize all distances to infinity, except the distance to the source node, which is set to 0.

2. Create a priority queue (min heap) to store nodes and their distances from the source node.

3. Add the source node to the priority queue with distance 0.

4. While the priority queue is not empty:

- Remove the node with the minimum distance from the priority queue.

- For each neighbor of the node:

- Calculate the distance to the neighbor through the current node.

- If this distance is less than the previously recorded distance to the neighbor, update the distance array and add the neighbor to the priority queue.

5. Repeat step 4 until the priority queue is empty.

Let's implement this algorithm using the Java Stream API:

import java.util.*;

public class ShortestPathFinder {
public List<Integer> findShortestPath(Graph graph, int source, int destination) {
Map<Integer, Integer> distances = new HashMap<>();
Map<Integer, Integer> previousNodes = new HashMap<>();
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(distances::get));

graph.getNodes().forEach(node -> {
distances.put(node, node == source ? 0 : Integer.MAX_VALUE);
previousNodes.put(node, null);
priorityQueue.add(node);
});

while (!priorityQueue.isEmpty()) {
int currentNode = priorityQueue.poll();

if (currentNode == destination) {
break;
}

List<Graph.Edge> edges = graph.getEdges(currentNode);

for (Graph.Edge edge : edges) {
int newDistance = distances.get(currentNode) + edge.getWeight();
if (newDistance < distances.get(edge.getDestination())) {
distances.put(edge.getDestination(), newDistance);
previousNodes.put(edge.getDestination(), currentNode);
priorityQueue.add(edge.getDestination());
}
}
}

List<Integer> shortestPath = new ArrayList<>();
Integer currentNode = destination;

while (currentNode != null) {
shortestPath.add(currentNode);
currentNode = previousNodes.get(currentNode);
}

Collections.reverse(shortestPath);

return shortestPath;
}

public static void main(String[] args) {
Graph graph = new Graph();
graph.addNode(0);
graph.addNode(1);
graph.addNode(2);
graph.addNode(3);
graph.addNode(4);
graph.addNode(5);

graph.addEdge(0, 1, 4);
graph.addEdge(0, 2, 2);
graph.addEdge(1, 3, 5);
graph.addEdge(2, 4, 3);
graph.addEdge(3, 5, 2);
graph.addEdge(4, 5, 1);

ShortestPathFinder finder = new ShortestPathFinder();
List<Integer> shortestPath = finder.findShortestPath(graph, 0, 5);

System.out.println("Shortest Path: " + shortestPath);
}
}

In this implementation, we use two maps (distances and previousNodes) to store the shortest distances from the source node and the previous node in the shortest path, respectively. We also use a priority queue to keep track of the nodes with their current distances. The algorithm terminates when the destination node is removed from the priority queue, indicating that the shortest path to the destination has been found.

Conclusion

In this blog post, we explored how to find the shortest path between two nodes in a graph using the Java Stream API. We implemented Dijkstra's algorithm and used the Stream API to simplify some of the operations. Graph traversal and pathfinding algorithms are essential in various applications, including network routing, GPS navigation, and recommendation systems. Understanding these algorithms and their implementations can help you solve a wide range of problems in computer science.

Java Stream API : Find Shortest Path Between Two Nodes in a Graph

Finding the Shortest Path Between Two Nodes in a Graph Using Java Stream API

Introduction

Understanding the Problem

Representing the Graph

Finding the Shortest Path Using Java Stream API

Conclusion

Post a Comment

Contact Form