我对主要路径问题的回答是错误的，有人可以帮助我找到问题吗？

Question

问题链接：https://www.spoj.com/problems/PPATH/

问题的简要说明，

1) Construct a graph with prime numbers between 1000 and 9999.
2) Add an undirected edge between two numbers 'a' and 'b', if they differ only by one digit. 
EX: 1033 and 1733 differ only by one digit.
3) In that graph we need to find the length of the shortest path from the given source to the given destination.

我已经解决了上述问题，通过连接仅相差一个数字的数字来构造使用1000到9999之间的质数的图形。例如：1033和1733仅相差一位数字。我使用DFS和记忆法来找到最短的路径。对于某些输入，我得到的答案是错误的，比实际值大1，因为有1000个节点，我无法找出问题。如果有人帮助我解决问题，它将非常有帮助。

我知道此问题可以通过BFS解决，但我需要知道此问题出了什么问题。

以下程序打印错误答案的测试案例

17573 9973

实际答案：4我的代码输出：5

（（通过提交针对问题的BFS方法找到了实际答案，并且在SPOJ中被接受）。>>

import java.util.*;
import java.lang.*;
import java.io.*;


class FireEscapeRoutes_FIRESC {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception{
        int t = 1;
        while (t--!=0){
            int source = 7573;
            int destination = 9973;
            List<Integer> fourDigitPrimeNos = new ArrayList<>();
            Graph graph = new Graph(fourDigitPrimeNos.size());
            for(int i=1001;i<=9999;i++){
                if(isPrime(i)){
                    fourDigitPrimeNos.add(i);
                    //System.out.println(i);
                }
            }
            /*
             If two number 'a' and 'b' differ only by one digit then an edge is added.
             */
            for (int i=0;i<fourDigitPrimeNos.size();i++){
                for (int j=i+1;j<fourDigitPrimeNos.size();j++){
                    if(isSingleDistnace(fourDigitPrimeNos.get(i),fourDigitPrimeNos.get(j))){
                        graph.add(fourDigitPrimeNos.get(i),fourDigitPrimeNos.get(j));
                    }
                }
            }
            //System.out.println(graph.graph);
            Long minPath = graph.getShortestPath(source,destination);
            if(minPath!=Long.MAX_VALUE){
                System.out.println(minPath);
            }else{
                System.out.println("Impossible");
            }

        }
    }

    static boolean isSingleDistnace(int a, int b){
        String as = a+"";
        String bs = b+"";
        int ds = 0;
        for (int i=0;i<as.length();i++){
            if(!(as.charAt(i)==bs.charAt(i))){
                if(ds>=1){
                    return false;
                }
                ds++;
            }
        }
        if(ds==0){
            return false;
        }
        return true;
    }
    static boolean isPrime(int n){
        for (int i=2;i<=Math.sqrt(n);i++){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }
}

class Graph{
    int noOfVertices;
    HashMap<Integer,List<Integer>> graph;
    Graph(int v){
        noOfVertices = v;
        graph = new HashMap<Integer,List<Integer>>();
    }
    void add(int u,int v){
        if (!graph.containsKey(u)){
            graph.put(u,new ArrayList<>());
        }
        if(!graph.containsKey(v)){
            graph.put(v,new ArrayList<>());
        }
        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    Long getShortestPath(int start, int dest){
        HashMap<Integer,Long> visitedVsMinCost = new HashMap<>();
        Long min = Long.MAX_VALUE;
        min = getShortestPathUtil(start,dest,visitedVsMinCost);
        return min-1;


    }

    Long getShortestPathUtil(Integer start,Integer dest,HashMap<Integer,Long> visitedVsMinCost){

        if(start.equals(dest)){
            return 1l;
        }
        visitedVsMinCost.put(start, Long.MAX_VALUE);
        List<Integer> frnds = graph.get(start);
        Long min = Long.MAX_VALUE;
        for (Integer iThFrind:frnds){
            if(!visitedVsMinCost.containsKey(iThFrind)){
                Long shortestPathUtil = getShortestPathUtil(iThFrind, dest, visitedVsMinCost);
                //System.out.println(shortestPathUtil + " min " + min);
                min = Math.min(min, shortestPathUtil);

            }else {
                if(!visitedVsMinCost.get(iThFrind).equals(Long.MAX_VALUE)) {
                    min = Math.min(min, visitedVsMinCost.get(iThFrind)+1);
                }
            }
        }
        visitedVsMinCost.put(start,min);
        //System.out.println(min);
        if (min.equals(Long.MAX_VALUE)){
            return min;
        }
        return min+1;

    }
}

问题链接：https://www.spoj.com/problems/PPATH/问题的简要说明，1）构造一个质数介于1000和9999之间的图。2）在两个数字'a'之间添加无向边...

Answer 1

调试发布的代码是一项艰巨的任务。但是，DFS不是适合该工作的工具。要了解为什么DFS不是找到最短路径的好工具，请考虑以下简单图形：