Minimum Cost using Dijkstra by reducing the cost of an Edge

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

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

Run Code

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.