Java에서 최단 경로 구현

Question

나는 인접 행렬로 작업 중이며 그래프 내에서 최단 경로를 찾는 함수를 작성하려고합니다. 최소 스패닝 트리 함수를 작성하는 데 사용한 Prim 알고리즘을 수정하려고합니다.

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는 각 노드의 행렬입니다. 쓰기는 출력 파일에 쓰는 기능입니다.

Answer 1

배열의 인덱스는 0입니다. 그러나 처음 두 개의 루프는 1에서 시작 : 대한

(I = 1; 내가 < 노드; 내가 ++)

그래서이 가능성의 원인이됩니다 당신이 first=0를 시작할 때에 있기 때문에, 작동한다는 사실이 당신의 인접 행렬 AMatrix[current][i] != 0 대각선 (현재 == i)는 아마 0입니다하지만 당신은 다른 값이 0으로 알고리즘을 시작하면, 당신은 노드 누락 :, 또한 0

을 몇 가지 힌트 :

• 당신은 말합니다 : "weight [i] = 32767; // 가장 짧은 int ",하지만 이것은 가장 짧은 2^15 - 1이며 다음과 같이 더 잘 초기화됩니다 : weight[i] = Short.MAX_VALUE;. 가장 큰 int를 원한다면 비슷합니다 : weight[i] = Integer.MAX_VALUE;
• 모든 것은 테스트하기가 쉽지 않으며 객체 지향 코드가 아닙니다. 당신은 JUnit을 사용하여 단위 테스트를 작성할 수 있습니다. 또는 Domi가 주석에서 말한 것처럼 (예 : 일식 디버거와 같은) 코드 디버깅을 시도하십시오.
• 코드를 직접 작성하지 않았다면 이해하기가 조금 어렵습니다. 예를 들어, 코드가 무엇인지 설명하는 루프 위에 각각의 주석을 추가하십시오. 코드의 가독성은 빠른 작성보다 더 중요합니다. 코드를 여러 번 반복하지만 한 번만 쓰십시오.