다익스트라 알고리즘을 이용했습니다 ㅜㅜㅜ

분명히 시작점하고 끝점은 잘찾는것 같은데.....

경로를 출력을 잘 못합니다.ㅜㅜㅜㅜ

분명히 걸리는 시간은 정확하게 나오는데,
경로가 환승역에서 완전히 이상한대로 갑니다 ㅜㅜ

다익스트라 경로만 뭐가 잘못됫는지 파악해주시면안될까요 ㅜ?

맨밑에가 경로 알고리즘입니다.ㅜㅜㅜ


class Station {
            //station 클래스 선언!   (클래스와 객체 개념을 이용합니다..!)
   String station_name;  // 역이름
   int station_num;      // 역번호         
     
   Station(int num, String name) {                  //Station의 생성자 메소드 선언.
     station_num = num;
     station_name = name;
     
     
   }
 }


import java.io.*;

public class Station_line {

 public static void main(String [] args) throws IOException {
     
     int a;
     int b;
     int c;
                  //카운터 a,b,c,d형성
     String start_enter;
     String end_enter;
     int start =0 ;
     int end = 0;
       
     int m = 10000;           //null값 역할을 하는 m 선언
     
     int i,j,k=0;
     float min;         //카운터 i,j,k 선언하기       for문에서 이용할 min값 사용 (= m값이 null값으로 쓸 쑤 잇게 하기..!)
     int [] v = new int[40];   //v[]선언 하기. data배열에서  열이 계산 됫는지 안됫는지 유무 파악하는 기능 배열
     float [] distance = new float[40]; //distance[]선언하기. 실제 거리 배열
     int [] via = new int[40]; 
     float data[][]={
      {0,4,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {4,0,4,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,4,0,7,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,7,0,9,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,9,0,3,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,3,0,5,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,5,0,5,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,5,0,3,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,3,0,5,3,2,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,5,0,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,3,m,0,m,m,5,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,2,m,m,0,m,m,4,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,0,4,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,5,m,4,0,2,m,m,m,m,m,m,4,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,4,m,2,0,5,m,m,m,m,m,m,5,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,5,0,2,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2,0,2,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2,0,5,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,5,0,2,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2,0,4,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,4,0,m,m,m,m,m,m,m,m,m,m,2,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,4,m,m,m,m,m,m,m,0,m,m,m,4,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,5,m,m,m,m,m,m,m,0,m,m,m,5,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0,2,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2,0,2,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,4,m,m,2,0,2,m,m,m,m,m,2,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,5,m,m,2,0,4,m,m,m,m,m,2,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,4,0,4,m,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,4,0,2,m,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2,0,4,m,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,4,0,2,m,m,m,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2,m,m,m,m,m,m,m,m,m,2,0,m,m,m,m,m,m,m,40},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2,m,m,m,m,m,m,0,m,2,m,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2,m,m,m,m,m,m,0,m,1,m,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2,m,0,m,3,m,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1,m,0,m,2,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,3,m,0,5,m,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2,5,0,3,m},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,3,0,4},
      {m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,10,m,m,m,m,m,m,4,0},
      };
    String[] names = new String[40] ;
   names[0] = "소요산";
   names[1] = "동두천"; 
   names[2] = "동두천중앙"; 
   names[3] = "덕정";
   names[4] = "양주"; 
   names[5] = "녹양"; 
   names[6] = "의정부"; 
   names[7] = "망월사"; 
   names[8] = "도봉산"; 
   names[9] = "장암"; 
   names[10] = "수락산"; 
   names[11] = "도봉"; 
   names[12] = "당고개"; 
   names[13] = "노원"; 
   names[14] = "창동"; 
   names[15] = "수유"; 
   names[16] = "미아"; 
   names[17] = "미아삼거리"; 
   names[18] = "성신여대입구"; 
   names[19] = "한성대입구"; 
   names[20] = "동대문"; 
   names[21] = "하계"; 
   names[22] = "월계";
   names[23] = "봉화산";
   names[24] = "화랑대";
   names[25] = "태릉입구";
   names[26] = "석계";
   names[27] = "상월곡";
   names[28] = "고려대";
   names[29] = "안암";
   names[30] = "창신";
   names[31] = "동묘앞";
   names[32] = "먹골";
   names[33] = "신이문";
   names[34] = "중화";
   names[35] = "외대앞";
   names[36] = "상봉";
   names[37] = "회기";
   names[38] = "청량리";
   names[39] = "신설동";
                 //이걸 한번에 표시할 수 있는.. 포토샵 같은게 필요해!
   Station[] stations = new Station[40] ;
   for(a=0;a<40;a++) {
     stations[a] = new Station(a,names[a]);
   }                                               //http://ddogani.blog.me/50083572952 객체배열 감사합니다.
   
   BufferedReader br = new BufferedReader( new InputStreamReader( System.in ));
   
  
        //bufferedReader 클래스의 사용.( 입력 스트림)
    System.out.print(" 출발역을 입력하세욧! : " );
    

    start_enter = br.readLine()  ;
    
    for(b=0;b<40;b++) {
      
      if(start_enter.equals(stations[b].station_name)) {
      start = b;
      stations[b] = new Station(b,names[b]);
     
      }
    }
    
    System.out.print(" 도착역을 입력하세욧! : "  ); 
   
    end_enter = br.readLine();
    for(c=0;c<40;c++) {
      if(end_enter.equals(stations[c].station_name)) {
        end = c;
     
      }
    }
                                                      // start,end 값에 입력값 받기.
       
      
        
    
    for( j=0; j<40; j++ ) { 
      v[j] = 0;  
      distance[j] = m;
    }                                            //초기화하기
    
    distance[start] = 0;                           // 자기 자신과의 역거리는 0이므로 0으로 선언한다..!
    
    
    for( i=0; i<40; i++ ) { 
      min = m;  
      for( j=0; j<40; j++ ) {  
        if( v[j] == 0 && distance[j] < min ) {    //v[]의 역할은 그 열이  실행됬으면 다시하지 않는 역할.
          k = j; 
          min = distance[j];                                
        }                                            //data[][] 에서 s지점 구하기.
      }                                           //distance가 s값을 받으면서 자기 자신의 위치 '0'을 사용 함으로써 자기 자신의 위치를 처음에
                                                   //
      v[k] = 1;                                       //  그래서 여기에 1을 넣어 줌으로써 안한 0 을 다시 for문 돌면서 처리 하는거지
      if(min==m) break;    // 
      
      for(j=0; j<40; j++) {   
        if(distance[j] > distance[k] + data[k][j]) {   //data[k][j]의 의미는 k번 역에서 j번 역으로 가는  거리임...! 즉 distance[j]는 null값 역할을 하는
          distance[j] = distance[k] + data[k][j];     via[j]=k;    //m에 v[]값을 이용해 구해진 k열에그리고 ditance[k]는 0임 언제나..!자기자신임..!
        }                                           // s가 있는 행의 배열 구하기.   distance[] s가 있는 행의 배열이 되는거지                                                  //= 이말이 뭘 뜻하는 거냐면,   1번에서 갈 수 있는 역을  말하는 거지.
      } 
    }  // 이거 i있는 포문에  끝이여.  i의 역할은 s역에서 ?역까지   반복문으로 다하 는거야  초기값은  위치찾고  다음에는 1역 2역...순서대로 찾는거지.
       // 이 for문은 i가 7까지 돌면서 시작점에서 을 찾아서 넣고, v[]값을 이용해서 차례차례  그 열에 해당하는 distance를 구하는 방법...!
    System.out.println(stations[start].station_name + "에서 출발하여, "  + stations[end].station_name + "로 가는  최단 시간은 "  +distance[end]+" 분 입니다.");  
    
     //via[]값이 의미하는 것 이해하기...!
    int path[] = new int[40];  
    int path_cnt=0; 
    k=end; 
   
    while(true) {                       //무한 루프 선언.
      path[path_cnt++]=k; 
      if(k==start)break;                    //끝점과 시작점이 같다면 필요없겟지.
      k=via[k];                             //via[]은 i를 받아오는 거잔아  거기 까지 몇번 돌았는지를 확인하는 배열이야.
    }
    
    
    System.out.print(" 경로는 : "); 
    for(i=path_cnt-1;i>=1;i--) { 
      System.out.print(stations[path[i]+1].station_name +" -> "); 
    }  
    System.out.printf(stations[path[i]+1].station_name +"입니다"); 
   
 
 
 
 
 
 }
   }