Travel maximum cities in given time limit

Issue

There are N cities represented as vertices from 1 to N

We can travel from one city to another in a given time. This is represented by edges as arrays U and V where (U[i], V[i]) represent an edge and time required to travel this edge is represented by T[i]

Now I should always start the travel from 1 and end at N in a given limited time TimeLimit, and cover the maximum number of cities from 1 to N.

Print the number of cities covered and the corresponding vertices in the order we can visit the cities.

Example 1:

N = 3, TimeLimit = 15
U = [1,2]
V = [3,3]
T = [9, 7]

Output:

2
1 3

Explanation:

we can start from 1 and reach 3 in time 9 which is less than the allowed time limit of 15

So cities are 1, 3 and so the number of cities is 2

Example 2:

N = 5, TimeLimit = 6
U = [1,3,1,2,4]
V = [3,5,2,4,5]
T = [3,3,2,3,2]

Output:

3
1 3 5

Explanation:

we can start from 1 and reach 3 in time 3 in time 3
we can continue to travel from city 3 to city 5 in time 3. So the total time is 3+3 = 6, so our time limit is 6. So valid path

So the cities covered are 1,3,5 and so the number of cities is 3.

What is the correct approach to solve this program?

Update:

I want to travel from the source city 1 to the destination city N. We have different paths to travel that take some time while traveling we will connect to other cities in between. The question is the maximum number of cities we can cover during this travel with a limitation that I need to reach the destination at the specified time limit. Hope this helps. If it is still not clear, please let me know so I will add more details.

Solution

This is a pretty common path finding routine. You could perform this by using a 'depth first search' which means we'll take every path and go all the way to the end, or until it exceeds time.

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class Pathfinder{

    public static void main(String[] args){
        int goal = 5;
        int timeLimit = 6;
        int[] U = {1,3,1,2,4};
        int[] V = {3,5,2,4,5};
        int[] T = {3,3,2,3,2};

        int edges = U.length;
        List<int[]> path = new ArrayList<>();

        //node, search, time
        int[] link = { 1, -1, 0};
        path.add(link);
        List<int[]> valid = new ArrayList<>();

        while(path.size() > 0){
            int[] last = path.get(path.size() - 1);
            int[] next = null;
            for(int o = last[1] + 1; o<edges; o++){
                if(U[o] == last[0]){
                    int time = T[0];
                    if( time + last[2] <= timeLimit ){
                        //valid step.
                        next = new int[]{ V[o], -1, last[2] + time};
                        //keep track of what we searched
                        last[1] = o;
                        break;
                    }
                }
            }
            if(next == null){
                //we've exhausted this path
                path.remove(path.size() - 1);
            } else{
                if( next[0] == goal ){
                    //we found our goal!
                    int[] cities = new int[path.size() + 1];
                    for(int j = 0; j<path.size(); j++){
                        cities[j] = path.get(j)[0];
                    }
                    cities[path.size()] = goal;
                    valid.add(cities);
                    //this is the end, so don't add next to the path.
                } else{
                    path.add(next);
                }
            }
        }
        for(int[] cs: valid){
            System.out.println(Arrays.toString(cs));
        }
    }

}

When that code finishes, all of the paths that start at 1 and end at the goal will be in the array list cities.

Answered By - matt