Find Shortest path of a weighted graph where weight is 1 or 2 in Java

In this article, we will discuss how to Find the Shortest path of a weighted graph where weight is 1 or 2 in Java. So you are given a directed weighted graph where every edge weight is either one or two and you have to find the shortest possible path. You can solve this by any single source shortest path algorithm like Dijkstra’s shortest path algorithm. But the time complexity must be O(E+VlogV). But in this tutorial, we will solve in O(E+V) time complexity.

Find the Shortest Path Of A Weighted Graph Where Weight Is 1 Or 2 in Java

First, understand with an example. Consider the graph given below.

Suppose the source is 0 and the destination is 5, so the shortest path is 0 ->1 -> 2 -> 5 and the cost is 4.

Algorithm:

You can solve this with any single source shortest path algorithm but here we will solve with BFS only.

The trick is to divide the edge of weight 2 to two edges of weight 1. Then do BFS of the graph and find the shortest path between source and destination.

Here, you have to declare a graph whose size is twice of total vertices. The extra space will be used for extra vertices generated from the edge of weight 2. Suppose edge weight from vertex 1 to 2 is two, so here we divide the edge. The first edge is from vertex 1 to (1+V) and the next edge is from (1+V) to 2, where V=total vertices.

That’s why we declare a graph whose size is twice of V.

Now let’s see the implementation-

import java.util.*; 

class Solution
{ 

  // This class represents a directed graph using adjacency 
  // list representation 
  static class Graph 
  { 
    int V; // No. of vertices 
    Vector<Integer>[] adj; // Adjacency List declaration 

    Graph(int k) 
    { 
      this.V = k; 
      this.adj = new Vector[2 * k]; 

      for (int i = 0; i < 2 * k; i++) 
        this.adj[i] = new Vector<>(); 
    } 
        
        //function for adding edge

    public void add(int v, int w, int weight) { 
 //if weight is two then devide the edge in two edges of weight one
      if (weight == 2) 
      { 
        adj[v].add(v + this.V); 
        adj[v + this.V].add(w); 
      } else 
        adj[v].add(w); 
    } 
        

    public void getShortestPath(int src, int dest) { 
            boolean[] vis = new boolean[2 * this.V]; //also decalre a vis array to store if the vertex is visited or not
            


      int[] parent = new int[2 * this.V]; //declare a parent array to store the parent of every vertex

      for (int i = 0; i < 2 * this.V; i++) 
      { 
        vis[i] = false; 
        parent[i] = -1; 
      } 


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

      vis[src] = true; 
      queue.add(src); 
//do a BFS traveral of graph
      while (!queue.isEmpty()) { 


        int s = queue.peek(); 

        if (s == dest) 
          break;
                queue.poll(); 
                
        for (int i : this.adj[s]) 
        { 
          if (!vis[i]) 
          { 
            vis[i] = true; 
            queue.add(i); 
            parent[i] = s; 
          } 
        } 
     } 


//declare a vector to store the shortest path
            Vector vec=new Vector();


//store every parent from destination to source vertex
            int cost=0;
            while(parent[dest]!=-1){
                cost++;
                if(dest<this.V)
                    vec.add(dest);
                dest=parent[dest];
            }
            vec.add(src);
            Collections.reverse(vec);
            System.out.print("The path is: ");

//traverse the v vector in reverse order vector to get the path
            Iterator i = vec.iterator();
                while (i.hasNext()) {
                   System.out.print(i.next()+" ");
                }
               
 
            System.out.println("And total cost:"+ cost);

        } 
        
  } 

  public static void main(String[] args) 
  { 

    int V = 6; 
    Graph graph = new Graph(V); 
    graph.add(0, 1, 1); 
    graph.add(0, 3, 2); 
    graph.add(1, 2, 2); 
    graph.add(3, 2, 1); 
    graph.add(3, 4, 1); 
    graph.add(4, 5, 1); 
    graph.add(2, 5, 1); 

    int src = 0, dest = 5; 
    graph.getShortestPath(0,5);

  } 
} 

Output:
The path is: 0 1 2 5 And total cost:4