Path Finding using Dynamic Programming

Question

I was trying to implement a dp + graph problem. After completing the solution I tried to compare it with solution in tutorial to figure out which one was better and to find a way to improve mine if I could. But I was not able to figure out which one is better, so please help. And if there is a way to improve my algorithm please tell me how I can do so.

Solution in tutorial

Author's solution uses dynamic programming. Let dpi, j be the minimum time required to arrive at the vertex i, if we visit j vertices (including vertices 1 and i). We have a DAG (directed acyclic graph), so we can compute it recursively (and memory constraints were a bit strict in this problem, so it's better to use recursion to compute it). Let's store the transposed version of the graph: if we had an edge (u, v) in the input, we will store (v, u). Then our function calc(i, j), which will compute the answer for dpi, j, will be like that: the base of dynamic programming is dp1, 1 = 0, all other states are equal to «-1». If we call calc(i, j), then it will work like that: if the state we want to compute is incorrect (j < 0), we return a very large integer number (any number that is greater than 109, because T ≤ 109). If the answer for this state has already been calculated, then we return dpi, j (it is easy do determine: if dpi, j ≠  - 1, then it has already been calculated). Else we begin to calculate the state. Firstly, let's put INF (a number greater than 109) into dpi, j. Then look at all the edges beginning in i and try to update dpi, j with the value of calc(to, j - 1) + w (to is the vertex at the endpoint of current edge, w is the weight of this edge). If this value is less than dpi, j, then we update dpi, j and store the information that our last update in dpi, j was from the vertex to. If we try to go by path which doesn't end in the vertex 1, then we get a value which is greater than 109, that's because that the only value we didn't denote as  - 1 is dp1, 1. So, now we have our calc function, let's compute the answer. We will iterate on the number of vertices in the path from n to 1 in descending order, and if calc(n, i) ≤ T, then we have found the answer, now we iterate on the parent vertices we stored while calculating our dp, until we come to vertex 1 (it's important because some participants sent solutions that continued even past vertex 1!) and print the answer.

My implementation of problem

#include<iostream> using namespace std; #define INT_MAX 5000 int getAns(int,int); int n,a[INT_MAX][INT_MAX],dp[2][INT_MAX]; int main(){ int m,t,u,v,time; cin>>n>>m>>t; for(int i=0;i<m;i++){ cin>>u>>v>>time; a[u][v]=time; } cout<<1+getAns(t,1)<<endl; int i=1; while(dp[1][i]!=0){ cout<<i<<" "; i=dp[1][i]; } cout<<i; } int getAns(int time,int curr){ if(time<0) return 0; for(int i=1;i<=n;i++){ if(a[curr][i]!=0&&a[curr][i]<=time){ int x=1+getAns(time-a[curr][i],i); if(dp[0][curr]<x){ dp[0][curr]=x; dp[1][curr]=i; } } } return dp[0][curr]; } 

Answer 1

How to compare the the Algorithms:

Either determine the complexity of your algorithm and the complexity of the solution in the tutorial.

If you want to avoid to determine the complexity based on the source code you can simply implement the tutorial solution and compare the runtime of your algorithm and the runtime of the of the tutorial-algorithm. To get a good idea of the complexity behavior of both algorithms you need inputs of different lengths to approximate the runtime related to the size of the input.

How to improve yours
If your approach is very different you might not be able to improve your algorithm by looking on the tutorial-algorithm because they are too different.
If the Tutorial-algorithm is better at all, you can try to understand the steps it does and try to memorize the general idea of this steps for your next algorithms that address similar problems.