Hi!
There are lot of problems related with finding the shortes or the longest path in graph, most of them using forms of DFS,BFS or in case of weighted graph using the Dijkstra algorithm, Bellman-Ford or one of the many other. Let’s see one of those problem:
Given a weighted –no negative weights– connected graph and two vertices, f and t, you’re asked to find the shortes path from f to t, but the cost of moving from a given node to the neighbour is not necessarily equal to its weight, but it may be divided by 2 if you drink a magic potion. You have k of those magic potions, you cannot cumulate their effect –cannot drink twice on the same edge in order to divide by 4 its weight-. You’re asked to find the shorted path with the best possible usage of those magic potions.
So we have the graph and k potions, we may relax up to k edges dividing its weight by 2. This problem is solvable using a slightly modified version of a DFS algorithm, what we shall do is for each encountered edge check both the options, without using the potion and using the potion.
In this way we branch the code everywhere is possible checking all the possible strategy of potion usage for all the possible combination of edges in the path, keeping saved the one with shortes path value.
void find_path(int f,int t,int k,double d)
{
if(f==t){
r = min(d,r);
return;
}
if(vis[f]==true) return;
if(d>r) return ;
vis[f] = true;
for(int i{0};i<V;i++)
{
if(mp[f][i]==0) continue;
if(k>=1){
find_path(i,t,k-1, d + double(mp[f][i])*.5);
}
find_path(i,t,k, d + double(mp[f][i]));
}
vis[f] = false;
}
where mp is the adjacency matrix for the graph, and vis is a vector<bool> which I use to mark all the vertex already visited.
As you can see the code checks all the options and each time the t vertex is encountered the best solution to the problem found so far is saved in the variable r, which at the end will contain the result.
You should notice that the algorithm complexity grows exponentially to the size of the graph since we are unmarking the visited edges at the end of the function in order to check all the possible combination of edges in any possible circumstance (with or without the potion).
This very simple function is indeed very difficult to analyze, the algorithm is checking all the possible paths from f to t so the running time is proportional to the amount of those paths, you may have a look HERE for some details.
A much smarter aproach to solve this problem is possible just noting that during the exploration of the graph is possible to create a new virtual graph in which we consider the additional edges to ghost vertex with halved reaching cost.
The idea is to use a slightly modified version Dijkstra where we push in the priority queue items with the following information {vertex,cost,remaining-potions}, if we enter one of those vertex we may reach adjacent vertexes which have at least remaining-potions potion or the same amount +1 (if we use a new the potion).
The algorith will thus find the weight of the shortes path. This is the idea on paper:
Where for example B’ is the vertex B in which one potion was already used, as you can see from there we may only reach D’ or C’ and not D nor C –Cannot undo one potion usage operation-. Is important to notice that no new graph needs to be created tough, but only ghost vertex to the priority queue of the Dijkstra code.
The working code for the new implementation is the following:
double shortest_pah(int s,int d,int k,int V)
{
pr_queue::pqueue Q;
std::vector weight(V,pr_queue::undefined_weight);
weight[s] = 0;
Q.insert(s,0,0);
for(int i{1};i<V;i++)
{
Q.insert(i,pr_queue::undefined_weight,0);
}
while(Q.size()>0)
{
pr_queue::item cur = Q.extract();
for(int i{0};i<V;i++)
{
if(i==cur.vertex || mp[cur.vertex][i]==0)
continue;
if(weight[i] > (mp[cur.vertex][i] + cur.weight))
{
weight[i] = mp[cur.vertex][i] + cur.weight;
Q.change(i,cur.used_potions,weight[i]);
}
if(cur.used_potions < k && (weight[i] > (double(mp[cur.vertex][i])/2.0 + cur.weight)))
{
weight[i] = double(mp[cur.vertex][i])/2.0 + cur.weight;
Q.change(i,cur.used_potions + 1,weight[i]);
}
}
}
return weight[d];
}
As you can see this is the common shortest path algorithm with a minor modification required to take into account the magic potion usage. The algorithm will eventually push in the queue vertexes with halved distances and with a certain amount of used potions.
If is possible to reach a given destination with less weight via the new vertex then the container weight is updated as well as the vertex priority in Q, in short the algorithm does what I explained before with the paper draw of the solution.
In order to work a priority queue is of couse required, since the standard library does not provide a priority queue with a change priority function I’ve provided the algorithm with a queue implemented ad-hoc.
The priority queue is implemented using a simple min heap and frankly the change function may be optimized drastically, I will let you do the job as homework 🙂
The complexity of this algorithm is almost completely dependent on the way the priority queue is implemented, using a fibonacci heap allows the code to run with asymptotic complexity of O(E+VlgV).
Thanks for reading!