CODEWITHSUNDEEP
algorithmdata-structuresgraph-theoryshortest-pathdijkstra
Anirban Saha
Anirban Saha

Reputation: 31

Shortest path in a Graph by reducing the Weight of multiple edges by half

Given a directed graph with positive edge weights, a source vertex, a destination vertex, and a integer M (M < 10), find the shortest path from the source to the destination. The twist is that M discounts are available, which can halve the weight of an edge. Each discount can be used only once. What is the shortest path that utilizes these discounts optimally?"

I tried the brute force recursive approach, but it may not be efficient for larger graphs. I am looking for a more efficient algorithm to solve this problem.

Upvotes: 3

Views: 130

Answers (3)

Unmitigated
Unmitigated

Reputation: 89412

You can still use Dijkstra's algorithm, but instead of storing the minimum distance to each vertex, store the minimum distance to each vertex for each possible number of discounts used. The state thus contains both the current vertex and the number of discounts used on the path from the source vertex to the current one.

At the end, consider the optimal distances to the destination vertex for each possible number of discounts and take the minimum one.

Example implementation in C++:

#include <vector>
#include <queue>
#include <algorithm>
struct Edge {
    int to, weight;
};
int solve(int nodes, int source, int dest, std::vector<std::vector<Edge>>& adj, int maxDiscounts) {
    std::vector<std::vector<int>> dist(nodes, std::vector<int>(maxDiscounts + 1, 1e9 /* larger than any possible path */));
    struct State {
        int distance, node, discounts;
    };
    std::priority_queue<State, std::vector<State>,
        decltype([](const auto& s1, const auto& s2){return s1.distance > s2.distance;})> pq;
    pq.emplace(dist[source][0] = 0, source, 0);
    while (!pq.empty()) {
        auto curr = pq.top();
        pq.pop();
        if (dist[curr.node][curr.discounts] == curr.distance)
            for (auto [nextNode, weight] : adj[curr.node]) {
                if (curr.distance + weight < dist[nextNode][curr.discounts])
                    pq.emplace(dist[nextNode][curr.discounts] = curr.distance + weight, nextNode, curr.discounts);
                if (curr.discounts < maxDiscounts && curr.distance + weight / 2 < dist[nextNode][curr.discounts + 1])
                    pq.emplace(dist[nextNode][curr.discounts + 1] = curr.distance + weight / 2, nextNode, curr.discounts + 1);
            }
    }
    return std::ranges::min(dist[dest]);
}

Upvotes: 1

ravenspoint
ravenspoint

Reputation: 20596

  • Find the shortest path using Dijkstra
  • LOOP for M times
    • Find the longest hop in the path
    • Halve the longest hop and update
    • ENDLOOP over M

Upvotes: 1

m.raynal
m.raynal

Reputation: 3133

It's possible to compute the shortest path with discounts by creating a new graph that is (m+1) times bigger than the original one.

What you need to do is to "multiply" your graph, you need M+1 of them (one if no discount was used, one if one discount was used ... one if m discounts were used). So you now have M+1 graphs, let's connect them to each other.

For each edge in your original graph between v and v', with cost w, create an edge between v in the i_th graph and v' in the i+1_th graph, with cost w/2 ; and an edge between v in the i_th graph and v in the i+1_th graph of cost 0 (to represent the fact that we may not need to use all discounts)

Then compute the shortest path between the source vertex of the 0th graph to the destination vertex of the M_th graph.

The complexity is still "the same", we're still running a shortest path, but on a graph that is (m+1) times bigger.

Upvotes: 3

Related Questions