Design Graph With Shortest Path Calculator Solution in Java

Quick Links

Ah, the classic problem of finding the shortest path in a graph! It’s like trying to find the quickest route to the nearest coffee shop while avoiding that one friend who always wants to chat about their cat’s latest antics. You know, the one who thinks they’re a cat whisperer?

In this problem, we’re tasked with designing a graph and calculating the shortest path between two nodes. Imagine you’re navigating through a city with various roads (edges) connecting different locations (nodes). Your goal? To get from point A to point B in the least amount of time, all while dodging traffic jams and construction zones.

Code Solution


import java.util.*;

class Graph {
  public Graph(int n, int[][] edges) {
    graph = new List[n];
    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();
    for (int[] edge : edges)
      addEdge(edge);
  }

  public void addEdge(int[] edge) {
    final int u = edge[0];
    final int v = edge[1];
    final int w = edge[2];
    graph[u].add(new Pair<>(v, w));
  }

  public int shortestPath(int node1, int node2) {
    int[] dist = new int[graph.length];
    Arrays.fill(dist, Integer.MAX_VALUE);
    Queue> minHeap = new PriorityQueue<>(Comparator.comparing(Pair::getKey));

    dist[node1] = 0;
    minHeap.offer(new Pair<>(dist[node1], node1));

    while (!minHeap.isEmpty()) {
      final int d = minHeap.peek().getKey();
      final int u = minHeap.poll().getValue();
      if (u == node2)
        return d;
      for (Pair pair : graph[u]) {
        final int v = pair.getKey();
        final int w = pair.getValue();
        if (d + w < dist[v]) {
          dist[v] = d + w;
          minHeap.offer(new Pair<>(dist[v], v));
        }
      }
    }

    return -1;
  }

  private List>[] graph;
}

Approach Explanation

The code implements Dijkstra’s algorithm to find the shortest path in a weighted graph. Here’s a brief breakdown of the approach:

Graph Representation: The graph is represented using an adjacency list, where each node points to a list of pairs containing its neighbors and the corresponding edge weights.
Distance Initialization: An array dist is initialized to store the shortest distance from the starting node to all other nodes, with all distances set to infinity initially, except for the starting node which is set to zero.
Priority Queue: A min-heap (priority queue) is used to efficiently retrieve the next node with the smallest distance.
Relaxation: For each node, the algorithm checks its neighbors and updates their distances if a shorter path is found.
Termination: The process continues until the destination node is reached or all reachable nodes have been processed.

Time and Space Complexity

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

Real-World Example

Imagine you’re using a navigation app to find the quickest route to a concert. The app uses a graph to represent the roads and intersections, with weights assigned based on distance or estimated travel time. By applying the shortest path algorithm, the app can guide you through the least congested routes, ensuring you arrive just in time to catch your favorite band—without getting stuck behind that one friend who insists on taking the scenic route!