Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently asked questions
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
    add_edge(0, 1, 12);
    add_edge(0, 2, 2);
    add_edge(2, 1, 6);
    add_edge(2, 3, 18);
    add_edge(3, 6, 4);
    add_edge(6, 5, 12);
    add_edge(3, 5, 9);
    add_edge(1, 6, 7);
    add_edge(1, 4, 6);
    add_edge(4, 5, 11);

    // 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.


Previous article
STL-based BFS for competitive coding
Next article
Shortest path in a Matrix from top-left to bottom right-corner with neighbours exceeding at most K
Live masterclass