# 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

## Leave a Reply