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.
Example
2.
Approach
3.
Algorithm
4.
Implementation
4.1.
Program
4.2.
Output
5.
Time Complexity
6.
Space Complexity
7.
Key Takeaways
Last Updated: Mar 27, 2024

Minimum Cost using Dijkstra by reducing the cost of an Edge

Author Ishita Chawla
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Dijkstra's algorithm is for finding the shortest distance, or path, between a starting node to a target node in a weighted graph. Dijkstra's algorithm uses the weights of the edges to find the path that minimizes the overall distance between the source node and all other nodes. This is also known as the single-source shortest path algorithm. It is BFS(Breadth-First Search) using Priority Queue. 

This blog will discuss one such problem involving Djikstra’s algorithm: minimum cost using Dijkstra by reducing the cost of an edge.

Problem Statement

You are given an undirected graph containing ‘N’ nodes and ‘M’ edges, of the form {X, Y, Z}, such that ‘X’ and ‘Y’ are connected with an edge having a cost Z. Your task is to find the minimum cost to go from a source node 1 to a destination node N if you are allowed to reduce the cost of only one path during the traversal by 2.

Let us try to understand this with the help of simple examples.

Example

  •      N = 3

M = 4

Edges = {{1, 2, 2}, {2, 3, 1}, {1, 3, 9}, {2, 1, 6}}                   

The minimum cost is given by 2/2 + 1 = 1 + 1 = 2

  •      N = 3

M = 3

Edges = {{2, 3, 1}, {1, 3, 6}, {2, 1, 5}}

The minimum cost is given by 6/2 = 3

Approach

The basic idea is to consider every edge and check whether reducing its cost minimizes the overall cost or not. So to do this, we will break the path between the source node to the destination node into 2 parts. The first path will be from the source node to any vertex, say U, (1 to U), and the second path will be from destination node N to any vertex, say V, (N to V) for all U and V.

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

Algorithm

  • We will find the single source shortest path for all the vertices from source node 1 and store it in an array, say SOURCE_DISTANCE.
  • Then, find the single source shortest path for all the vertices from source node N, and store it in an array, say DESTINATION_DISTANCE.
  • We will store the minimum cost, in a variable MIN_COST, initially initialized as INT_MAX.
  • Then, traverse through all the edges and for each edge, reduce the current cost to half and then update the minimum cost according to:

Where  = Cost of Current edge

             SOURCE_DISTANCE[u] = Cost of path from node 1 to U.

             DESTINATION_DISTANCE[v] =  Cost of path from node V to N.

  • In the end, print this minimum cost, which is our required answer.

Implementation

Program

// C++ program to calculate the minimum cost using Dijkstra by reducing the cost of an edge.
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// Dijkstra's algorithm for finding the single source shortest path.
void dijkstra(int source, int n, vector<pair<int, int>> adj[], vector<int> &dist)
{
    // Resizing the distance vector and assigning a large value to it.
    dist.resize(n, INT_MAX);

    // The distance of the source node is initialised to 0.
    dist[source] = 0;

    // Using priority queue to implement min-heap and sort the edges according to the cost.
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    // Pushing the current distance and source into the priority queue.
    pq.push({dist[source], source});

    // Until this queue becomes empty.
    while (!pq.empty())
    {
        // Storing the cost of the linked node to the edges.
        int u = pq.top().second;

        // Popping out the top node.
        pq.pop();

        // Iterating over the edges.
        for (const pair<int, int> &edge : adj[u])
        {
            // Find the starting and ending vertices of the edges.
            int v = edge.first;
            int w = edge.second;

            // Updating the minimum distance of node v.
            if (dist[u] + w < dist[v])
            {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

// To find the minimum cost between the first and the n-th node.
void minimumPath(int nodes, int edges, vector<pair<int, pair<int, int>>> &edgeList)
{
    // Creating the adjacency list.
    vector<pair<int, int>> adj[100005];

    // Iterating over the edges.
    for (int i = 0; i < edges; i++)
    {
        adj[edgeList[i].first].push_back({edgeList[i].second.first, edgeList[i].second.second});
        adj[edgeList[i].second.first].push_back({edgeList[i].first, edgeList[i].second.second});
    }

    // Storing the cost from node 1 and node n.
    vector<int> distanceSource;
    vector<int> distanceDestination;

    // Calculating the cost of traversal between source(1) and other vertices.
    dijkstra(1, nodes + 1, adj, distanceSource);

    // Calculating the cost of traversal between destination(n+1) to any vertex.
    dijkstra(nodes, nodes + 1, adj, distanceDestination);

    // Initialising the minimum cost
    int minCost = INT_MAX;

    // Traversing the edges.
    for (const pair<int, pair<int, int>> &it : edgeList)
    {
        // Obtaining the edges.
        int u = it.first;
        int v = it.second.first;
        int c = it.second.second;

        /*/ Finding the current cost from the 1-st node to the u-th node and the u-th node
        to the v-th node and the v-th node to the n-th node with only the cost of the current
        edge being reduced to half./*/
        int currentCost = distanceSource[u] + c / 2 + distanceDestination[v];

        // Updating the minimum cost accordingly.
        minCost = min(minCost, currentCost);
    }

    // Printing the minimum cost.
    cout << minCost << '\n';
}

int main()
{
    // Nodes and edges.
    int nodes = 3;
    int edges = 4;

    // Edge list.
    vector<pair<int, pair<int, int>>> edgeList;

    edgeList.push_back({1, {2, 3}});
    edgeList.push_back({2, {3, 1}});
    edgeList.push_back({1, {3, 7}});
    edgeList.push_back({2, {1, 5}});

    // Calling the function and printing our answer.
    cout << "The minimum cost is ";
    minimumPath(nodes, edges, edgeList);

    return 0;
}

Output

The minimum cost is 2

Time Complexity

O(N + M), where N is the number of nodes and M is the total number of edges.

This problem uses Dijkstra’s algorithm, which uses BFS; the time complexity is the same as BFS, which is O(V + E), where V is the number of nodes and E is the number of edges.

Space Complexity

The space complexity is given by O(N), where N is the number of nodes.

Since a priority queue is used to implement Djikstra’s Algorithm, so the space complexity is given by O(N).

Key Takeaways

So, this blog discussed the problem of calculating the minimum cost using Dijkstra by reducing the cost of an edge. Visit Coding Ninjas Studio to practice problems on topics like Graphs and Trees and crack your interviews like a Ninja!

Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our mock tests and see which areas need improvement.

Feel free to post any suggestions in the comments section.

Previous article
Maximize the shortest path between given vertices by adding a single edge
Next article
Minimum Number of Swaps Required to Sort an Array
Live masterclass