![Shortest path in a graph]()
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 = 3
0 → 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:
So we need a faster approach.
Optimized Idea
Notice something important.
The graph contains only two edge weights:
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:
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;
}
}
Code Explanation
Step 1
int extra = 0;
for (int[] e : edges) {
if (e[2] == 2)
extra++;
}
Explanation
Counts how many edges have weight 2.
Each weight-2 edge needs one extra node.
Example
Edges:
There are 2 weight-2 edges.
So:
extra = 2
Step 2
int totalNodes = V + extra;
Suppose:
V = 5
extra = 3
Then:
Total Nodes = 8
because we inserted 3 new vertices.
Step 3
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
Creates the adjacency list.
Example:
graph[0] -> 1,4
graph[1] -> 0,2
graph[2] -> 1,3
Step 4
int newNode = V;
The first inserted node starts after the original vertices.
Example:
Original nodes:
0 1 2 3
New nodes begin from:
4
Step 5
if (w == 1)
A normal edge.
0 -----1----- 1
Store:
because the graph is undirected.
Step 6
else
Weight = 2
Instead of:
0 -----2----- 2
Convert to:
0 ----4---- 2
Actually stored as:
Now every edge has weight 1.
Step 7
int[] dist = new int[totalNodes];
Arrays.fill(dist, -1);
Creates the distance array.
Initially:
-1
means:
Not Visited
Step 8
Queue<Integer> q = new LinkedList<>();
Creates the queue used for BFS.
Step 9
q.offer(src);
dist[src] = 0;
Starts BFS.
The source distance is always:
0
Step 10
while (!q.isEmpty())
Continue until every reachable node has been visited.
Step 11
int node = q.poll();
Removes the front node from the queue.
Step 12
if (node == dest)
return dist[node];
If the destination is reached, return the shortest distance immediately.
Step 13
for (int next : graph.get(node))
Visit every neighbor.
Step 14
if (dist[next] == -1)
If the neighbor has not been visited, visit it.
Step 15
dist[next] = dist[node] + 1;
Since every transformed edge has weight 1, the distance increases by one.
Step 16
q.offer(next);
Push the neighbor into the queue.
Step 17
return -1;
If BFS finishes and the destination is not found, there is no path.
Dry Run
Input
V = 4
Edges:
0-1 (1)
0-2 (2)
2-3 (1)
1-2 (1)
1-3 (2)
Transformation
0 --1-- 1
|
4
|
2 --1-- 3
1 --5-- 3
Inserted nodes:
BFS
Initial Queue:
0
Visit:
0
Distance:
0 = 0
Neighbors:
Queue:
1 4
Visit:
1
New nodes:
Queue:
4 2 5
Visit:
2
Neighbor:
3
Distance:
3
Answer: 3
Complexity Analysis
Graph Construction
BFS
Overall Time Complexity
Auxiliary Space
Key Interview Points
Since edge weights are restricted to 1 or 2, we avoid Dijkstra's O((V + E) log V) complexity.
Convert every weight-2 edge into two weight-1 edges by introducing one intermediate vertex.
After transformation, the graph becomes unweighted, allowing BFS to compute the shortest path.
The transformation preserves the total path cost, so the BFS result matches the original weighted shortest distance.
This approach achieves the expected O(V + E) time complexity.
Summary
When a graph contains only edge weights 1 and 2, we can transform every weight-2 edge into two weight-1 edges by introducing an intermediate vertex. This converts the weighted graph into an unweighted graph, allowing Breadth-First Search (BFS) to compute the shortest path in O(V + E) time. The transformation preserves the original path costs, making BFS both correct and more efficient than Dijkstra's algorithm for this specific problem.