우선 결론적으로는 이 문제는 다익스트라 알고리즘을 활용하여서
해결하였는데, 처음에 작성한 소스코드가 왜 작동이 안하는지 몰라서 질문드립니다.

bool path[1000][1000];
bool visit[1000];
int cache[1000],n;const int INF = 987654321;
int counts[1000];

int dp(int index)
{
if(index==n-1) return 0;

int &ret = cache[index],i;
if(ret!=-1) return ret;

visit[index]= true;
ret= INF;

for(i=0;i<n;++i)
    if(path[index][i] && !visit[i])
        ret= min(ret, 1+ dp(i));

visit[index]=false;

return ret;

}

int backtrack(int current,int w)

{

if(index==n-1) return 1;

int &ret= counts[index],next;
if (ret!=-1) return ret;
ret= 0;

for(next=0;next<n;++next)
    if(path[current][next] && 1+cache[next]==w)
        ret =max(ret, backtrack(next,w-1));

return ret;

}
(입력받는 부분은 생략)

dfs와 dp 를 활용하여서 각 index 에서 n-1 까지 가는 최단경로를 기억해 놓는
방식으로 알고리즘을 작성했습니다.

그리고 구해진 최단경로는 cache라는 배열에 저장해 놓았고요. cache 는 -1로 초기화한 상태입니다.

그리고 backtrack 이라는 함수를 활용하여서 현재 current 에서 n-1 번 정점까지의 최단경로의 길이 W가 있을때,

current에서 next 까지의 경로가 존재하면서 next 에서 n-1 번 정점까지의 거리를 의미하는 cache[next] + 1 ( 1은 current 에서 next 까지의 거리)

이 W와 같다면 재귀적으로 탐색을 시도하는 알고리즘인데요.

여기서 만일 n-1 번까지 이어지게 된다면 1값을 받게 됩니다.

혹시 제 알고리즘이나 소스코드에 문제점을 알려주실수 있나요?

긴 글 읽어주셔서 감사합니다.