Given a weighted undirected graph consisting of N nodes and M edges, the task is to find the shortest distance between two nodes A and B by reducing the weight of one edge by half.
Examples:
Input: A = 0, B = 2, Below is the graph
Output: 8
Explanation:
After reducing the weight of the edge connecting 1 and 2 by half modifies its new weight to 4. Now, the shortest distance to reach 2 from 0 through the path 0 -> 1 -> 2 is (4 + 4) = 8.
Therefore, print 8.
Approach: The given problem can be solved by maintaining two arrays, the shortest distance array taking source node as A which will store the shortest distance of all nodes from A, and similarly the shortest distance array taking source node as B. These arrays can be calculated using Dijkstra’s algorithm. Follow the below steps to solve the above problem:
- Use Dijkstra’s algorithm to store the shortest distance of each node from A into an array disA[].
- Use Dijkstra’s algorithm to store the shortest distance of each node from B into an array disB[].
- Suppose edgei = {ui, vi, wti} i.e., edgei connects node ui to vi and has a weight of wti.
- Now, iterate over all edges and for every edge keep track of the function as:
f(edgei) = min( disA[ui] + disB[vi], disA[vi] + disB[ui]) + (wti/2).
- The above relation gives the minimum value of f(edge), which is the resultant shortest distance.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Stores the input Graphvector<pair<int, int> > graph[100001];// Stores edges of input Graphvector<vector<int> > edges;// Function to input Edgesvoid add_edge(int u, int v, int w){ graph[u].push_back({ v, w }); graph[v].push_back({ u, w }); edges.push_back({ u, v, w });}// Function to find the shortest distance// to each node from the src node using// Dijkstra’s Algorithmvector<int> dijsktras(int src, int N){ // Stores the shortest distance of // each node form src node vector<int> dis(N, INT_MAX); vector<bool> vis(N, false); // Stores the node and current // minimum distance in a heap priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; pq.push({ 0, src }); dis[src] = 0; // BFS for single source shortest // path algorithm while (!pq.empty()) { // Top of the PQ auto cur = pq.top(); pq.pop(); // Store the node and weight int node = cur.second; int weight = cur.first; // If node is already visited if (vis[node]) continue; vis[node] = true; // Traverse the adjacency list // of the node for (auto child : graph[node]) { // If the distance obtained // from parent is less than // the current minimum // distance stored for child if (dis[child.first] > child.second + weight) { dis[child.first] = weight + child.second; // Push the next pair // in the PQ pq.push({ dis[child.first], child.first }); } } } // Return the maximum distance return dis;}// Function to find shortest distance// between two nodes by reducing any// one weight of an edge by halfint shortestDistance(int N, int M, int A, int B){ // Stores the shortest distance // of each node from A vector<int> disA = dijsktras(A, N); // Stores the shortest distance // of each node from B vector<int> disB = dijsktras(B, N); int ans = disA[B]; for (auto edge : edges) { int u = edge[0], v = edge[1]; int weight = edge[2]; // Calculate the value of f(edge) // for the current edge int cur = min(disA[u] + disB[v], disA[v] + disB[u]) + (weight / 2); // Keep track of the minimum of // f(edge) for all edges ans = min(ans, cur); } // Return Answer return ans;}// Driver Codeint main(){ int N = 9, M = 14, A = 0, B = 2; // Create a Graph add_edge(0, 1, 4); add_edge(1, 2, 8); add_edge(2, 3, 7); add_edge(3, 4, 9); add_edge(4, 5, 10); add_edge(5, 6, 2); add_edge(6, 7, 1); add_edge(7, 0, 8); add_edge(1, 7, 11); add_edge(7, 8, 7); add_edge(2, 8, 2); add_edge(6, 8, 6); add_edge(2, 5, 4); add_edge(3, 5, 14); // Function Call cout << shortestDistance(N, M, A, B); return 0;} |
Java
// jav program for the above approachimport java.util.*;// Stores the input Graphpublic class ShortestPathWithHalfEdgeWeight {// Stores edges of input Graph static List<List<Pair>> graph = new ArrayList<>(); static List<List<Integer>> edges = new ArrayList<>(); static void addEdge(int u, int v, int w) { graph.get(u).add(new Pair(v, w)); graph.get(v).add(new Pair(u, w)); edges.add(Arrays.asList(u, v, w)); // Function to find the shortest distance// to each node from the src node using// Dijkstra’s Algorithm } // Stores the shortest distance of // each node form src node static class Pair implements Comparable<Pair> { int first, second;// Stores the node and current // minimum distance in a heap Pair(int f, int s) { first = f; second = s; }// If the distance obtained // from parent is less than // the current minimum // distance stored for child public int compareTo(Pair o) { return Integer.compare(first, o.first); } } // Function to find shortest distance// between two nodes by reducing any// one weight of an edge by half static List<Integer> dijkstras(int src, int N) { List<Integer> dis = new ArrayList<>(Collections.nCopies(N, Integer.MAX_VALUE)); List<Boolean> vis = new ArrayList<>(Collections.nCopies(N, false)); PriorityQueue<Pair> pq = new PriorityQueue<>(); pq.add(new Pair(0, src)); dis.set(src, 0); // Stores the shortest distance // of each node from B while (!pq.isEmpty()) { Pair cur = pq.poll(); int node = cur.second, weight = cur.first; if (vis.get(node)) continue; vis.set(node, true); for (Pair child : graph.get(node)) { if (dis.get(child.first) > child.second + weight) { dis.set(child.first, weight + child.second); pq.add(new Pair(dis.get(child.first), child.first)); } } } return dis; } static int shortestDistance(int N, int M, int A, int B) { List<Integer> disA = dijkstras(A, N); List<Integer> disB = dijkstras(B, N); int ans = disA.get(B); for (List<Integer> edge : edges) { int u = edge.get(0), v = edge.get(1), weight = edge.get(2); int cur = Math.min(disA.get(u) + disB.get(v), disA.get(v) + disB.get(u)) + (weight / 2); ans = Math.min(ans, cur); } return ans; }// Driver Code public static void main(String[] args) { int N = 9, M = 14, A = 0, B = 2; for (int i = 0; i < N; i++) { graph.add(new ArrayList<>()); }// Create a Graph addEdge(0, 1, 4); addEdge(1, 2, 8); addEdge(2, 3, 7); addEdge(3, 4, 9); addEdge(4, 5, 10); addEdge(5, 6, 2); addEdge(6, 7, 1); addEdge(7, 0, 8); addEdge(1, 7, 11); addEdge(7, 8, 7); addEdge(2, 8, 2); addEdge(6, 8, 6); addEdge(2, 5, 4); addEdge(3, 5, 14); // Function Call System.out.println(shortestDistance(N, M, A, B)); }} |
Python
import heapqimport sys# Stores the input Graphgraph = [[] for i in range(100001)]# Stores edges of input Graphedges = []# Function to input Edgesdef add_edge(u, v, w): graph[u].append((v, w)) graph[v].append((u, w)) edges.append((u, v, w))# Function to find the shortest distance# to each node from the src node using # Dijkistra Algorithmdef dijsktras(src, N): # Stores the shortest distance of # each node form src node dis = [sys.maxsize] * N vis = [False] * N # Stores the node and current # minimum distance in a heap pq = [(0, src)] dis[src] = 0 # BFS for single source shortest # path algorithm while pq: # Top of the PQ weight, node = heapq.heappop(pq) # If node is already visited if vis[node]: continue vis[node] = True # Traverse the adjacency list # of the node for child, child_weight in graph[node]: # If the distance obtained # from parent is less than # the current minimum # distance stored for child if dis[child] > child_weight + weight: dis[child] = weight + child_weight # Push the next pair # in the PQ heapq.heappush(pq, (dis[child], child)) # Return the maximum distance return dis# Function to find shortest distance# between two nodes by reducing any# one weight of an edge by halfdef shortest_distance(N, M, A, B): # Stores the shortest distance # of each node from A disA = dijsktras(A, N) # Stores the shortest distance # of each node from B disB = dijsktras(B, N) ans = disA[B] for u, v, weight in edges: # Calculate the value of f(edge) # for the current edge cur = min(disA[u] + disB[v], disA[v] + disB[u]) + (weight // 2) # Keep track of the minimum of # f(edge) for all edges ans = min(ans, cur) # Return Answer return ans# Driver Codeif __name__ == "__main__": N, M, A, B = 9, 14, 0, 2 # Create a Graph add_edge(0, 1, 4) add_edge(1, 2, 8) add_edge(2, 3, 7) add_edge(3, 4, 9) add_edge(4, 5, 10) add_edge(5, 6, 2) add_edge(6, 7, 1) add_edge(7, 0, 8) add_edge(1, 7, 11) add_edge(7, 8, 7) add_edge(2, 8, 2) add_edge(6, 8, 6) add_edge(2, 5, 4) add_edge(3, 5, 14) # Function Call print(shortest_distance(N, M, A, B)) |
C#
using System;using System.Collections.Generic;namespace ConsoleApp1{ class Program { static void Main(string[] args) { int N = 9, M = 14, A = 0, B = 2; var graph = new List<Tuple<int, int, int>>(); graph.Add(new Tuple<int, int, int>(0, 1, 4)); graph.Add(new Tuple<int, int, int>(1, 2, 8)); graph.Add(new Tuple<int, int, int>(2, 3, 7)); graph.Add(new Tuple<int, int, int>(3, 4, 9)); graph.Add(new Tuple<int, int, int>(4, 5, 10)); graph.Add(new Tuple<int, int, int>(5, 6, 2)); graph.Add(new Tuple<int, int, int>(6, 7, 1)); graph.Add(new Tuple<int, int, int>(7, 0, 8)); graph.Add(new Tuple<int, int, int>(1, 7, 11)); graph.Add(new Tuple<int, int, int>(7, 8, 7)); graph.Add(new Tuple<int, int, int>(2, 8, 2)); graph.Add(new Tuple<int, int, int>(6, 8, 6)); graph.Add(new Tuple<int, int, int>(2, 5, 4)); graph.Add(new Tuple<int, int, int>(3, 5, 14)); Console.WriteLine(ShortestDistance(graph, N, M, A, B)); Console.ReadLine(); } private static int ShortestDistance(List<Tuple<int, int, int>> graph, int N, int M, int A, int B) { var distA = Dijkstras(graph, N, A); var distB = Dijkstras(graph, N, B); int ans = distA[B]; foreach (var edge in graph) { int u = edge.Item1; int v = edge.Item2; int weight = edge.Item3; int cur = Math.Min(distA[u] + distB[v], distA[v] + distB[u]) + (weight / 2); ans = Math.Min(ans, cur); } return ans; } private static int[] Dijkstras(List<Tuple<int, int, int>> graph, int N, int src) { var dis = new int[N]; for(int i=0; i<N; i++) { dis[i] = Int32.MaxValue; } var vis = new bool[N]; var pq = new SortedSet<Tuple<int, int>>(Comparer<Tuple<int, int>>.Create((x, y) => x.Item1.CompareTo(y.Item1))); pq.Add(new Tuple<int, int>(0, src)); dis[src] = 0; while(pq.Count > 0) { var cur = pq.Min; pq.Remove(cur); int node = cur.Item2; int weight = cur.Item1; if (vis[node]) continue; vis[node] = true; foreach (var child in graph) { if(child.Item1 == node || child.Item2 == node) { int adjNode = child.Item1 == node ? child.Item2 : child.Item1; if (dis[adjNode] > child.Item3 + weight) { dis[adjNode] = weight + child.Item3; pq.Add(new Tuple<int, int>(dis[adjNode], adjNode)); } } } } return dis; } }} |
Javascript
// Stores the input Graphconst graph = [];const edges = [];function addEdge(u, v, w) { graph[u] = graph[u] || []; graph[v] = graph[v] || []; graph[u].push([v, w]); graph[v].push([u, w]); edges.push([u, v, w]);}// Function to find the shortest distance// to each node from the src node using// Dijkstra’s Algorithmclass Pair { constructor(first, second) { this.first = first; this.second = second; } // If the distance obtained from parent is less than // the current minimum distance stored for child compareTo(o) { return this.first - o.first; }}// Function to find shortest distance between two nodes by reducing any// one weight of an edge by halffunction dijkstras(src, N) { const dis = new Array(N).fill(Number.MAX_SAFE_INTEGER); const vis = new Array(N).fill(false); const pq = []; pq.push(new Pair(0, src)); dis[src] = 0; // Stores the shortest distance of each node from B while (pq.length > 0) { const cur = pq.shift(); const node = cur.second; const weight = cur.first; if (vis[node]) continue; vis[node] = true; for (const child of graph[node]) { const [v, w] = child; if (dis[v] > w + weight) { dis[v] = w + weight; pq.push(new Pair(dis[v], v)); } } } return dis;}function shortestDistance(N, M, A, B) { const disA = dijkstras(A, N); const disB = dijkstras(B, N); let ans = disA[B]; for (const edge of edges) { const [u, v, weight] = edge; const cur = Math.min(disA[u] + disB[v], disA[v] + disB[u]) + Math.floor(weight / 2); ans = Math.min(ans, cur); } return ans;}// Create a GraphaddEdge(0, 1, 4);addEdge(1, 2, 8);addEdge(2, 3, 7);addEdge(3, 4, 9);addEdge(4, 5, 10);addEdge(5, 6, 2);addEdge(6, 7, 1);addEdge(7, 0, 8);addEdge(1, 7, 11);addEdge(7, 8, 7);addEdge(2, 8, 2);addEdge(6, 8, 6);addEdge(2, 5, 4);addEdge(3, 5, 14);// Function Callconst N = 9, M = 14, A = 0, B = 2;console.log(shortestDistance(N, M, A, B)); |
Output:
8
Time Complexity: O(M*log N)
Auxiliary Space:O(N + M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
