Я получаю неправильный ответ на проблему первичного пути. Может ли кто-нибудь помочь мне найти проблему?

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, соединяя номера, которые отличаются только на один ди git. Пример: 1033 и 1733 отличаются только на одну ди git. Я использовал DFS вместе с запоминанием, чтобы найти кратчайший путь. Для некоторого ввода я получаю неправильный ответ, на 1 больше, чем фактическое значение, так как есть 1000 узлов, я не могу выяснить проблему. Будет очень полезно, если кто-нибудь поможет мне разобраться в проблеме.

Я знаю, что эту проблему можно решить с помощью BFS, но мне нужно знать, что не так с этой проблемой.

контрольные примеры когда приведенная ниже программа печатает неправильный ответ

1
7573 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<>();

            for(int i=1001;i<=9999;i++){
                if(isPrime(i)){
                    fourDigitPrimeNos.add(i);
                    //System.out.println(i);
                }
            }
            Graph graph = new Graph(fourDigitPrimeNos.size());
            /*
             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;

    }
}

ПРИМЕЧАНИЕ. Эта часть ниже объясняет, почему мой код работает в ситуации, упомянутой @ c0der. Поскольку я не могу комментировать больше символов, я редактирую этот вопрос. Чтобы понять подход, вы можете использовать эту часть ниже.

Я могу понять, что отладить код сложно, поэтому я пытаюсь объяснить свой подход, используя график, упомянутый в ответе @coder, и код выше работает нормально в упомянутом вами сценарии.

Start = 1 и destination = 5, кратчайший путь = 2 (1-> 4-> 5)

1), если DFS проходит через `1-> 2 -> 3-> 4-> 5 'и достигли пункта назначения' 5 ', он возвращает' 1 'в' 4'-узел.

2) теперь '4'-узел запоминает возвращаемое значение' 1' . (Это означает, что между 4 и 5 существует один узел, включая пункт назначения, исключая источник 4).

2.1) Затем он возвращает «2» (1 + 1) в «3» -ый узел. и «3-й узел» запоминает значение «2». (Это означает, что между 3-м узлом и узлом назначения (5) в самом коротком пути есть 2 узла. Включая пункт назначения, исключая источник 3

3). Аналогично вызов go вернется к '1'.

4) затем «1-й узел» вызывает 4-й узел и видит, что он посещался ранее, поэтому он принимает запомненное значение «4-го узла», равное «1», и возвращает «2» на «1».

Answer 1

Отладка размещенного кода - долгая задача. Однако DFS не является подходящим инструментом для работы. Чтобы понять, почему DFS не является хорошим инструментом для поиска кратчайшего пути, рассмотрим следующий простой график:

Если DSF запускается при обходе узлов 1->2->3->4->5 кратчайший путь 1->4->5 не будет пройден, потому что 4 помечен как посещенный. Это может быть причиной того, что DFS вместе с запоминанием не может найти кратчайший путь.

---

---

Редактировать: Ниже приведена измененная версия вашего кода: он возвращает фактический кратчайший путь, если таковой имеется. Это может помочь в отладке. Если находит кратчайший путь, выполняя DFS для обхода всех возможных путей и сохраняя кратчайший путь.
Он не оптимизирован в том смысле, что при наличии циклов в графе он может пересчитать путь, который уже был рассчитан ранее. Вы можете добавить запоминание рассчитанных путей, чтобы сделать его более эффективным.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class FireEscapeRoutes_FIRESC {

    public static void main(String[] args) throws Exception{

        List<Integer> fourDigitPrimeNos = new ArrayList<>();

        for(int i=1001; i<=9999; i++){
            if(isPrime(i)){
                fourDigitPrimeNos.add(i);
            }
        }

        Graph graph = new Graph();
        /*
             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));
                }
            }
        }

        int source = 1033; 
        int destination = 8179;  //expected 6 : 1033  1733  3733  3739  3779  8779  8179

        /* more test cases
        int source = 7573;
        int destination = 9973; //expected 5

        int source = 1373;
        int destination = 8017; //expected 7

        int source = 1033;
        int destination = 1033; //expected 1
        */
        List<Integer> shortestPath = graph.getShortestPath(source,destination);

        if(shortestPath != null){
            System.out.println("\nPath Found :"+ shortestPath);
            System.out.println("Path length: "+shortestPath.size());
        }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){

        if (n <= 1) return false; //make sure it is positive

        for (int i=2;i<=Math.sqrt(n);i++){
            if(n%i==0)
                return false;
        }
        return true;
    }
}

class Graph{

    private final HashMap<Integer,List<Integer>> graph;
    //measure time and print out some progress indication
    private static long startTime, printime;
    private static long HEART_BEAT = 15000;

    Graph(){
        graph = new HashMap<>();
    }

    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);
    }

    List<Integer> getShortestPath(int start, int dest){

        System.out.print("Working ");
        startTime = System.currentTimeMillis();

        List<Integer> path = new ArrayList<>();
        path = getShortestPathUtil(start,dest, Integer.MAX_VALUE, path);

        System.out.println("\n run time in minutes " + (double) (System.currentTimeMillis() - startTime) /60000);
        return path;
    }

    List<Integer> getShortestPathUtil(int start,int dest,int minLengthFound, List<Integer> path){

        if(System.currentTimeMillis() - printime >= HEART_BEAT ){
            System.out.print(".");
            printime = System.currentTimeMillis();
        }

        if(path.contains(start)) return null; //prevent loops

        path.add(start);
        if(start == dest) return path;
        //stop traverse if path is longer than the shortest one found earlier
        if(minLengthFound != Integer.MAX_VALUE && path.size() >= minLengthFound) return null;

        List <Integer> keepShortestPathFound = null;
        for (int neighbor : graph.get(start)){

            if(path.contains(neighbor)) {
                continue;
            }

            List<Integer> shortestPathFromNeighbor = getShortestPathUtil(neighbor, dest, minLengthFound, new ArrayList<>(path));
            if(shortestPathFromNeighbor != null && shortestPathFromNeighbor.contains(dest) &&
                    shortestPathFromNeighbor.size() < minLengthFound){
                keepShortestPathFound = shortestPathFromNeighbor;
                minLengthFound = shortestPathFromNeighbor.size();
            }
        }

        return keepShortestPathFound;
    }
}