I found this problem on Codesignal,

Consider a big city located on n islands. There are bridges connecting the islands, but they all have only one-way traffic. To make matters worse, most of the bridges are closed at night, so there is at most one bridge with traffic going from any island A to any other island B.

There is a programmer who turns a penny by working nights as an Uber driver. One night his phone dies right after he picks up a rider going from island 0 to island (n - 1). He has the map of the city bridges in his laptop though (stored as a matrix of distances), so he decides to implement an algorithm that calculates the shortest path between those two islands and evaluate the cost based on the distance of the path. Assume that each mile of the trip is 1$.

Example

For

city = [[-1, 5, 20],
[21, -1, 10],
[-1, 1, -1]]
the output should be nightRoute(city) = 15.

city[i][j] equals the distance between the ith and the jth islands in miles, or -1 if there is no bridge by which one can move from island i to island j.

nightRoute(city) should be 15, since the shortest distance from the 0th to the 2nd island is 15. The distance from the 0th to the 1st is city[0][1] = 5, and from the 1st to the 2nd is city[1][2] = 10.

Now an obvious solution for this would be to use Dijkstra's algorithm, that worked. I wanted to implement this aith DFS using backtracking as well.

Here's my code

int nightRoute(int[][] city) 
{
    int dist=Integer.MAX_VALUE;
    boolean[][] visited=new boolean[city.length][city[0].length];
    for(int k=0;k<city[0].length;k++)
        if(city[0][k]!=-1)
            dist=Math.min(dist,dfs(city,visited,0,k,city[0][k]));
    return dist;
}

public int dfs(int[][] city, boolean[][] visited, int r, int c, int cost)
{
    if(c==city.length-1)
        return cost;
    visited[r][c]=true;
    int min=Integer.MAX_VALUE;
    for(int j=0;j<city[c].length;j++)
    {
        if(city[c][j]!=-1 && !visited[c][j])
            min=Math.min(min,dfs(city,visited,c,j,cost+city[c][j]));
    }
    visited[r][c]=false;
    return min;
}

This works for most of the testcases except for input
city:
[[-1,-1,19,8,18,-1,-1,-1,-1,-1],
[10,6,4,7,0,10,18,-1,0,-1],
[-1,-1,15,-1,17,3,-1,14,16,3],
[4,19,3,15,8,4,6,11,5,8],
[5,3,10,-1,0,14,15,1,16,5],
[-1,8,-1,-1,5,-1,5,0,1,-1],
[-1,18,-1,19,2,-1,10,-1,8,6],
[14,8,12,16,-1,-1,0,16,15,17],
[4,5,1,12,0,4,8,15,1,-1],
[13,7,17,-1,4,13,16,3,12,9]]

fo some reason, it's going in an infinite loop, I have been trying to figure this out for a long time now. Could someone take a look and point out where i messed up?

The algo is pretty straightforward, for every cell in the first row, if the value is not -1, run a backtracking based dfs that spans every possible path and computes the minimum.

Thanks in advance