Introduction
This blog will discuss the solution to this problem to find the shortest distance between two nodes in a graph by reducing the weight of an edge by half.
Problem Statement
Here we are given a weighted undirected graph that consists of N nodes and M edges. Our task is to find the shortest path between two nodes, A and B, by reducing the weight of one edge by half. So before we deep dive into the answer, we should look at some examples to understand the problem better.
Sample Example
Input:
A=0 and B=1 in the graph given below:
Output: 5
Explanation:
After reducing the weight of the edge connecting 2 and 1, the weight will be half, i.e., 3, so now the shortest path to reach 1 from 0 will be 0>2>1 is (2+3) = 5.
Approach
To solve this problem, find the shortest distance between two nodes in a Graph by reducing the weight of an edge by half; we will solve it by maintaining two arrays one array will store the shortest distance of all nodes from A, and another array will store the shortest distance of all nodes from B. These arrays will be calculated using Dijkstraâ€™s Algorithm.
Steps of algorithm
 We will use Dijkstraâ€™s Algorithm to store the shortest distance of each node from A, and we will store that distance in the array named distA[].
 We will use Dijkstraâ€™s Algorithm to store the shortest distance of each node from B, and we will store that distance in the array named distB[].
 Edge[i] = {u[i], v[i], wt[i]}, here u[i] and v[i] are the nodes which are connected by this edge and wt[i] is the weight of this edge.

Now, we will iterate over all the edges, and for every edge, we will keep track of the answer:
f(edge[i]) = min( distA[u[i]] + distB[v[i]], distA[v[i]] + distB[u[i]]) + (wt[i]/2).