Кратчайший путь реализации в Java

Question

Я работаю с матрицей Adjacency и пытаюсь создать функцию, которая находит кратчайший путь в графе. Я пытаюсь изменить алгоритм Prim, который я использовал для записи минимальной функции spanning tree.

public static int shortest(int first, int last) throws Exception{ 
       int weight[] = new int[Nodes.length]; //keeps track of the weights of the added edges 
       int path[] = new int[Nodes.length]; //keeps track of the nodes in the path 
       boolean visited[] = new boolean[Nodes.length]; //keeps track of nodes visited 
       int current; 
       int total; 
       int minWeight; 
       int nodes = Nodes.length; 
       int i; 

       for (i=0;i<nodes;i++){ //initialization 
        path[i]=0; 
        visited[i]=false; 
        weight[i]=32767; //largest short int 
       } 

       current=first; 
       weight[current]=0; 
       total=1; 
       visited[current]=true; 
       path[0]=current; 

       while(total!=nodes){ 
        for(i=1;i<nodes;i++){ 
         if(AMatrix[current][i] != 0 && visited[i]==false && weight[i]>AMatrix[current][i]){  
           weight[i]=AMatrix[current][i]; 
            path[i]=current; 
         } 
        } 
        minWeight=32767; 
        for(i=1;i<nodes;i++){ 
         if(visited[i]==false && weight[i]<minWeight){ 
          minWeight=weight[i]; 
          current=i; 
         } 
        } 
        write("current = "+ current); 
        visited[current]=true; 
        total++; 

        if(current == last){ 
         path[total-1]=current; 
         for(i=1;i<total;i++){ 
          write("includes the node "+Nodes[path[i]]); 
         } 

         minWeight=0; 
         int j=1; 
         for(i=2;i<total;i++){ 
          write("The weight from "+Nodes[path[j]]+" to "+Nodes[path[i]]+" is "+AMatrix[path[j]][path[i]]); 
          minWeight = minWeight+AMatrix[path[j]][path[i]]; 
          write("min weight= "+minWeight); 
          j++; 
         } 
         return minWeight; 
        } 
       } 

       return -1; 
     } 

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

На самом деле я думаю, что с этим связано много чего, например, если я попытаюсь распечатать элементы, начиная с массива путей от 0, он будет печатать первый раз дважды, поэтому я уверен, я сделал много ошибок, но это тот, который для меня совершенно очевидно.

AMatrix - это моя матрица смежности, а Nodes - матрица каждого из моих узлов. Запись - это функция I, которую я написал, что записывает в выходной файл.

Answer 1

Массивы имеют индексы на основе нуля. Но первые две петли начинаются с 1:

для (I = 1, я < узлов; я ++)

Так что это, скорее всего, вызовет тот факт, что он работает, когда вы начинаете first=0, потому что в Ваша матрица смежности AMatrix[current][i] != 0 диагонали (ток == я), вероятно 0. Но если начать алгоритм с другим значением, 0, вы упускаете узел: 0.

Кроме того, всего несколько советов:

• Вы скажете: "вес [i] = 32767; // наибольший короткий int ", но это самый большой короткий, 2^15 - 1, который лучше инициализируется следующим образом: weight[i] = Short.MAX_VALUE;. Если вы хотите наибольший int, это похоже: weight[i] = Integer.MAX_VALUE;
• Лучше не использовать статические для все, это непросто проверить, и это не OO. Возможно, вы можете написать модульный тест с помощью JUnit. Или, как сказал Domi в комментарии, попробуйте отладить ваш код (например, отладчик eclipse).
• Код немного трудно понять/понять, если вы его не пишете сами. Так что добавьте комментарии, например, выше каждого цикла, объясняя, что он делает. Читаемость кода важнее, чем быстро писать, потому что вы будете читать код несколько раз, но вы пишете его только один раз.