
Problem Statement
You are given an undirected weighted graph where every edge has a weight of either 1 or 2.
Your task is to find the minimum distance from the source vertex (src) to the destination vertex (dest).
If no path exists, return -1.
Example
0 --1-- 1
| |
2 2
| |
2 --1-- 3
Source: 0
Destination: 3
Possible Paths
0 → 1 → 3 = 1 + 2 = 30 → 2 → 3 = 2 + 1 = 3
Answer: 3
Naive Approach
We can use Dijkstra's Algorithm because the graph is weighted.
Complexity
Time:
O((V + E) log V)Space:
O(V)
However, the problem expects:
Time:
O(V + E)
So we need a faster approach.
Optimized Idea
Notice something important.
The graph contains only two edge weights:
Weight =
1Weight =
2
There are no other weights.
Instead of running Dijkstra's algorithm, we convert every weight-2 edge into two weight-1 edges.
After conversion, every edge has weight 1.
Now the graph becomes an unweighted graph.
For an unweighted graph:
BFS always finds the shortest path.
Graph Transformation
Suppose we have:
0 -----2------ 2
Insert one new vertex.
0 ----1---- X ----1---- 2
The total weight is still:
1 + 1 = 2
Nothing changes.
Another Example
Original
A -----2----- B
Converted
A ----1---- X ----1---- B
Now every edge weight is 1.
Why Does This Work?
Suppose the original shortest path is:
0 ----2---- 1 ----1---- 2
Distance = 3
After conversion:
0 --1-- X --1-- 1 --1-- 2
Distance = 3 edges
BFS counts edges.
Since every edge now has weight 1:
Number of edges = Total Weight
Hence, BFS returns the correct shortest distance.
Algorithm
Step 1
Count all weight-2 edges.
Suppose there are K such edges.
We need K new vertices.
Total vertices:
V + K
Step 2
Create an adjacency list.
ArrayList<ArrayList<Integer>>
Step 3
For every edge:
If:
weight == 1
Add it normally.
u ↔ v
Otherwise:
Create a new node X.
u ↔ X
X ↔ v
Step 4
Run BFS from the source.
Maintain:
distance[]
Initially:
distance[source] = 0
For every neighbor:
distance[child] = distance[parent] + 1
Step 5
Return:
distance[destination]
If the destination is never visited:
return -1
Code
import java.util.*;
class Solution {
public int shortestPath(int V, int src, int dest, int[][] edges) {
int extra = 0;
// Count weight-2 edges
for (int[] e : edges) {
if (e[2] == 2)
extra++;
}
int totalNodes = V + extra;
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i < totalNodes; i++)
graph.add(new ArrayList<>());
int newNode = V;
// Build transformed graph
for (int[] e : edges) {
int u = e[0];
int v = e[1];
int w = e[2];
if (w == 1) {
graph.get(u).add(v);
graph.get(v).add(u);
} else {
graph.get(u).add(newNode);
graph.get(newNode).add(u);
graph.get(newNode).add(v);
graph.get(v).add(newNode);
newNode++;
}
}
int[] dist = new int[totalNodes];
Arrays.fill(dist, -1);
Queue<Integer> q = new LinkedList<>();
q.offer(src);
dist[src] = 0;
while (!q.isEmpty()) {
int node = q.poll();
if (node == dest)
return dist[node];
for (int next : graph.get(node)) {
if (dist[next] == -1) {
dist[next] = dist[node] + 1;
q.offer(next);
}
}
}
return -1;
}
}

Join the conversation! Your thoughts help the community grow.