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

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;
}

You can also try this code with Online C++ Compiler

Run Code

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.