Thursday, October 9, 2014

a bit of graph dp: SPOJ - ROADS

Problem Statement:
SPOJ - ROADS

Summary:
Given a directed graph where each edge has attributes cost and distance, find the shortest distance possible from the vertex $$v_1$$ to $$v_N$$ while the total cost is at most $$K$$.
$$N \leq 100, K \leq 10^4, |E| \leq 10^4$$. Costs can be zero, and two nodes may be connected by multiple edges.

Solution:
I have two ways of solving this problem, firstly with a more intuitive and straight forward dynamic programming approach:
Let $$S(c, n)$$ be the shortest distance possible to reach vertex n from vertex 1 incurring at most c total cost. Then we have S(c, n) = min [for each edge v into n] { S(c-1, n), S(c - cost[v to n]) + dist[v to n] }
But we have to take care of the case where $$c = 0$$, which can be treated as a special case. We store another information of minimum distances between vertices which requires 0 cost to travel to. Then for each $$n$$, after taking care of updates required for all $$c \neq 0$$, we check each pairs of nodes if they are connected using 0 cost path, and update the distances accordingly.
This approach takes $$O(K(N^2+|E|))$$ time, and I am surprised that it is accepted by the judge.

The better solution is using Dijkstra algorithm by modeling vertices as representing states state[vertex, total cost already incurred]. We can have the similar table $$D(n, c)$$ representing the shortest distance required to travel from state[1, 0] to state[n, c]. Implementation using STL priority_queue is blazingly fast but take note that we need to terminate the algorithm once we have vertex N on top of our priority_queue since the corresponding distance is indeed the shortest distance.