Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach
2.1.
Steps of algorithm
3.
Implementation in C++
3.1.
Complexity Analysis
4.
5.
Key takeaways
Last Updated: Mar 27, 2024

# Shortest distance between two nodes in a Graph by reducing the weight of an edge by half

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## 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

1. 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[].
2. 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[].
3.  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.
4. 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).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Implementation in C++

``````// C++ code to find Shortest distance between two nodes in a Graph by reducing the weight of an edge by half

#include <bits/stdc++.h>
using namespace std;

// To store the input graph
vector<pair<int, int>> graph[100001];

// To store the edges of the graph
vector<vector<int>> edges;

// Function to add edges of the graph
void add_edge(int u, int v, int w)
{
edges.push_back({u, v, w});
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}

// Function to find the shortest distance
// for each node from the source node
vector<int> dijkstras(int source, int N)
{
// to store the shortest distance
// of each node from source node
vector<int> dist(N, INT_MAX);

// visited array to check if the node is visited or not
vector<bool> vis(N, false);

// to store the node and current distance in a heap
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

pq.push({0, source});
dist[source] = 0;

// BFS
while (!pq.empty())
{

auto cur = pq.top();
pq.pop();

// To store the node and weight of the edge
int node = cur.second;
int weight = cur.first;

// if the node is visited then jump to next node
if (vis[node])
continue;

vis[node] = true;

// to travere the adjacency list of the node
for (auto child_node : graph[node])
{

if (dist[child_node.first] > child_node.second + weight)
{
dist[child_node.first] = weight + child_node.second;

// push the next pair of child_node and the weight
pq.push({dist[child_node.first], child_node.first});
}
}
}

// The maximum distance
return dist;
}

// Function to find the shortest distance between two nodes in a Graph by reducing the weight of an edge by half
int shortestDistanceFromAandB(int N, int M,
int A, int B)
{
vector<int> distA = dijkstras(A, N);
vector<int> distB = dijkstras(B, N);

int ans = distA[B];
for (auto edge : edges)
{
int u = edge[0], v = edge[1];
int weight = edge[2];

// Calculate the f(edge)
int cur = min(distA[u] + distB[v],
distA[v] + distB[u]) +
(weight / 2);

// take the minimum of current answer and answer
ans = min(ans, cur);
}

// return the answer
return ans;
}

// Driver Code
int main()
{
int N = 7, M = 10, A = 0, B = 1;

// Create a Graph

// Function Call
cout << shortestDistanceFromAandB(N, M, A, B);

return 0;
}``````

Output:

``5``

### Complexity Analysis

Time Complexity: O(M*log(N))

Here M is the number of edges, and N is the no of nodes.

Space Complexity: O(N+M)

## Frequently asked questions

Q1. What are the nodes of the graph?

Ans- The nodes are the fundamental units by which a graph is formed. Nodes are also termed as vertices of the graph.

Q2. Can there be multiple shortest paths in a graph?

Ans- Yes, we can find multiple shortest paths in a Graph.

Q3. What is the edge of the graph?

Ans- Edge is the line that connects two nodes of the graph.

## Key takeaways

In this article, we discussed the problem of finding the shortest distance between two nodes in a Graph by reducing the weight of an edge by half. We have discussed its approach based on Dijkstra's algorithm, and we have also discussed the time and space complexities of the approach. Now, itâ€™s your turn to solve this problem by own.
Until then, Keep Learning and Keep Coding.

Live masterclass