다익스트라에서 경로 출력 문제 질문합니다.

Question

package teamproject; import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class Dijkstra { int Inf &#61; 100; int graphnumber &#61; 0; String teamname; // 다른vertex간 엣지 // 존재시 가중치 값 n public Dijkstra(String teamname) { this.teamname &#61; teamname; } public void makegraph(String fileName) { int[] Bestdistance; // vertex의 최단 경로가 지정될때마다 갱신될 정보를 저장할 배열 int[][] Edge; // 가중치 배열 boolean[] visited; // 방문 배열 int start &#61; 0; // 시작 정점(항상 1번 노드) int[] saveRoute; // 경로를 저장 try (Scanner scan &#61; new Scanner(new File(fileName))) { while (scan.hasNextLine()) { int a &#61; scan.nextInt(); // 노드의 개수 int number &#61; a; // 노드 개수 saveRoute &#61; new int[number]; visited &#61; new boolean[a]; // 방문 배열 Bestdistance &#61; new int[a]; Edge &#61; new int[a][a]; // 시작 꼭지점에서 각 꼭지점으로의 값 모두 초기화 무한대로 for (int i &#61; 0; i < number; i&#43;&#43;) { Bestdistance[i] &#61; Inf; } Bestdistance[start] &#61; 0; visited[start] &#61; true; // 시작 노드 방문 처리 saveRoute[start] &#61; start &#43; 1; while (scan.hasNextLine()) { // 다음 읽은 값이 노드개수이면 결과를 출력하고 break String str &#61; scan.nextLine(); String[] temp &#61; str.split(&#34; &#34;); int[] numarr &#61; new int[temp.length]; for (int i &#61; 0; i < temp.length; i&#43;&#43;) { try { numarr[i] &#61; Integer.parseInt(temp[i]); } catch (NumberFormatException e) { } } for (int i &#61; 1; i < numarr.length; i &#43;&#61; 2) { // 2 3 4 5 try { if (numarr[i] !&#61; 0) { // 0 7 4 6 1 Edge[numarr[0] - 1][numarr[i] - 1] &#61; numarr[i &#43; 1]; } } catch (ArrayIndexOutOfBoundsException e) { } } if (str.equals(Integer.toString(a))) { graphnumber&#43;&#43;; break; } } for (int i &#61; 0; i < number; i&#43;&#43;) { if (Edge[0][i] !&#61; 0 && !visited[i]) { Bestdistance[i] &#61; Edge[start][i]; saveRoute[i] &#61; 1; // 시작 꼭지점과 인접한 꼭지점의 경로에 시작 꼭지점을 저장 } } for (int i &#61; 0; i < number - 1; i&#43;&#43;) { int minDistance &#61; Inf; // 최단거리 minDistance에 일단 가장 큰 정수로 저장하고, int minVertex &#61; -1; // 그 거리값이 있는 인덱스 minIndex에 -1을 저장해둔다. for (int j &#61; 0; j < number; j&#43;&#43;) { // 방문하지 않았고 거리를 갱신한 꼭지점 중에서 가장 가까운 거리와 가장 가까운 꼭지점을 구한다. if (!visited[j]) { if (Bestdistance[j] < minDistance) { minDistance &#61; Bestdistance[j]; minVertex &#61; j; } } } visited[minVertex] &#61; true; // 위의 반복문을 통해 도출된 가장 가까운 꼭지점에 방문 표시 for (int j &#61; 0; j < number; j&#43;&#43;) { // 방문하지 않았고 minVertex와의 가중치가 존재하는(minVertex에서 연결된) 꼭지점이라면 if (!visited[j] && Edge[minVertex][j] !&#61; 0) { // 지금 그 꼭지점이 가지고 있는 거리값이 minVertex와 가중치를 더한 값보다 크다면 최단거리 갱신 if (Bestdistance[j] > Bestdistance[minVertex] &#43; Edge[minVertex][j]) { Bestdistance[j] &#61; Bestdistance[minVertex] &#43; Edge[minVertex][j]; saveRoute[j] &#61; minVertex &#43; 1; // 최단거리가 갱신된 꼭지점의 경로에 minVertex에 해당하는 꼭지점 저장 } } } } System.out.println(&#34;그래프 &#34; &#43; graphnumber); System.out.println(&#34;--------------------&#34;); System.out.println(&#34;시작점: &#34; &#43; (start &#43; 1)); for (int i &#61; 0; i < number; i&#43;&#43;) { String route &#61; &#34;&#34;; if (i !&#61; 0) { System.out.print(&#34;정점 [&#34; &#43; (i &#43; 1) &#43; &#34;] : &#34;); } int index &#61; i; while (true) { if (saveRoute[index] &#61;&#61; index &#43; 1) { break; // 시작 꼭지점일 경우 break } route &#43;&#61; &#34; - &#34; &#43; Integer.toString(saveRoute[index]); index &#61; saveRoute[index] - 1; // 결정적인 역할을 한 꼭지점을 int형으로 바꿔서 index에 저장 } StringBuilder sb &#61; new StringBuilder(route); // route를 합쳐서 sb에 한꺼번에 저장 if (i !&#61; 0) { System.out.print(sb.reverse() &#43; Integer.toString(i &#43; 1) &#43; &#34;, 길이: &#34; &#43; Bestdistance[i]); // sb를 } System.out.println(); } System.out.println(&#34;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#61;&#34;); System.out.println(); } } catch (FileNotFoundException e) { System.out.println(teamname &#43; &#34;의 그래프 배열이 생성되지 않았습니다.
파일명을 확인하세요.&#34;); } } } 정점 [6]에 대해서 답이 1 2 3 6도 답이 되는데 1 2 3 6으로 답이 나오게 하는 방법이 있나요?저는 saveRoute 배열에 최소경로가 새롭게 탐색될 때 갱신하도록 하였습니다.

다익스트라에서 경로 출력 문제 질문합니다.

0개의 답변

기타 목록