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.

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

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

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. VisitCoding Ninjas Studio to practice problems on topics like GraphsandTrees 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 testsand see which areas need improvement.

Feel free to post any suggestions in the comments section.