```
import java.util.Scanner;
public class Chdan2 {
public static void main(String[] args) {
int m = 999;
String[] state = { "서울", "원주", "강릉", "천안", "논산", "대전", "대구", "포항", "광주", "부산" };
int[][] data = { { m, 15, m, 12, m, m, m, m, m, m }, // 서울
{ 15, m, 21, m, m, m, 7, m, m, m }, // 원주
{ m, 21, m, m, m, m, m, 8, m, m }, // 강릉
{ 12, m, m, m, 4, 10, m, m, m, m }, // 천안
{ m, m, m, 4, 3, m, m, m, 13, m }, // 논산
{ m, m, m, 10, 3, m, 10, m, m, m }, // 대전
{ m, 7, m, m, m, 10, m, 19, m, 9 }, // 대구
{ m, m, 25, m, m, m, 19, m, m, 5 }, // 포항
{ m, m, m, m, 13, m, m, m, m, 10 }, // 광주
{ m, m, m, m, m, m, 9, 5, 15, m } }; // 부산
boolean flag = true;
Scanner scan = new Scanner(System.in);
//String name = "";
int[][] nodeArray = null;
int[] distance = null;
int[] temp = null;
int[] via = null;
int index = -1;
int node = 0;
int min = 0;
int num = 0;
String str = "";
while(flag) {
System.out.print("1.필요한 그래프의 노드 수를 입력하세요 : ");
node = scan.nextInt();
nodeArray = new int[node][node];
distance = new int[node];
via = new int[node];
System.out.println("2.(입력한 갯수만큼의 행 입력하기)");
for(int i=0; i<nodeArray.length; i++) {
System.out.printf("%s행 : ", (i+1));
for(int j=0; j<nodeArray[i].length; j++) {
str = scan.next();
if(str.equals("m")) {
nodeArray[i][j] = m;
}else {
nodeArray[i][j] = Integer.parseInt(str);
}
}
}
System.out.println("3.입력한 행을 보여주며");
for(int i=0; i<nodeArray.length; i++) {
System.out.printf("%s행 : ", (i+1));
for(int j=0; j<nodeArray[i].length; j++) {
if(j > 0) System.out.print(" ");
if(nodeArray[i][j] == m) {
System.out.printf("%2s", "m");
}else {
System.out.printf("%2s", String.valueOf(nodeArray[i][j]));
}
}
System.out.println();
}
System.out.print("→ 잘못된 입력사항이 있습니까? 의사 물어보기(Yes or No) : ");
str = scan.next();
if(str.equalsIgnoreCase("YES")) {
continue;
}
index = 2;
while(true) {
System.out.println();
System.out.print("출발 노드를 입력하시오 : ");
str = scan.next();
for(int i=0; i<str.length(); i++) {
if(str.equals(state[i])) {
index = i;
break;
}
}
if(index == -1 || index > node) {
System.out.println("그것은 올바르지 않은 출발 노드입니다. 다시 입력해주세요");
continue;
}
break;
}
temp = new int[node];
for (int i=0; i<nodeArray.length; i++) {
for (int j=0; j<distance.length; j++) {
temp[j] = 0;
distance[j] = m;
}
distance[0] = 0;
for (int j=0; j<distance.length; j++) {
min = m;
for (j = 0; j <node; j++) {
if (temp[j] == 0 && distance[j] < min) {
num = j;
}
min = distance[j];
}
}
temp[num] = 1;
if (min == m) break;
for (int j=0; j<distance.length; j++) {
if (distance[j] > distance[num] + data[num][j]) {
distance[j] = distance[num] + data[num][j];
via[j] = num;
}
}
}
System.out.println("5. 최간경로 + 최단거리 값");
for(int i=index; i<nodeArray.length; i++) {
System.out.printf("%s에서 출발하여, %s로 가는 최단비용은 %d입니다.\n", state[index], state[i], distance[i]);
}
System.out.print("6. 재시작 (Yes or No); : ");
str = scan.next();
if(str.equalsIgnoreCase("No")) {
flag = false;
}
}
scan.close();
}
}
```
이게 현재 까지 만든 소스입니다
하지만 distance 값이 0 으로 초기화되던가 아니면 999로 입력됩니다.
제가 배열을 짜서 입력을했을때 노드의 갯수만큼 최단경로가떠야 되는데
수정을 못하겠습니다.
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
1.필요한 그래프의 노드 수를 입력하세요 : 3
2.(입력한 갯수만큼의 행 입력하기)
1행 : m 15 m
2행 : 15 m 21
3행 : m 21 m
3.입력한 행을 보여주며
1행 : m 15 m
2행 : 15 m 21
3행 : m 21 m
→ 잘못된 입력사항이 있습니까? 의사 물어보기(Yes or No) : No
출발 노드를 입력하시오 : 서울
5. 최간경로 + 최단거리 값
서울에서 출발하여, 서울로 가는 최단비용은 0입니다.
서울에서 출발하여, 원주로 가는 최단비용은 999입니다.
서울에서 출발하여, 강릉로 가는 최단비용은 999입니다.
6. 재시작 (Yes or No); :
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 이렇게가 아닌
1.필요한 그래프의 노드 수를 입력하세요 : 3
2.(입력한 갯수만큼의 행 입력하기)
1행 : m 15 m
2행 : 15 m 21
3행 : m 21 m
3.입력한 행을 보여주며
1행 : m 15 m
2행 : 15 m 21
3행 : m 21 m
→ 잘못된 입력사항이 있습니까? 의사 물어보기(Yes or No) : No
출발 노드를 입력하시오 : 대전
그것은 올바르지 않은 출발 노드입니다. 다시 입력해주세요
출발 노드를 입력하시오 : 서울
5. 최간경로 + 최단거리 값
서울에서 출발하여, 서울로 가는 최단비용은 0입니다.
서울에서 출발하여, 원주로 가는 최단비용은 15입니다.
서울에서 출발하여, 강릉로 가는 최단비용은 36입니다.
6. 재시작 (Yes or No); :
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
으로 수정하고싶습니다.
```
import java.util.Scanner;
public class ShortestPath {
public static void main(String[] arg) {
int n = 10;
int m = 5000;
int i, j, k = 0, s = 0, e = 0, min;
int[] v = new int[10];
int[] distance = new int[10];
int[] via = new int[10];
String[] array = { "서울", "천안", "원주", "대전", "논산", "강릉", "광주", "대구", "부산", "포항" };
int[][] data = { { 0, 12, 15, m, m, m, m, m, m, m }, // 1. 서울
{ 2, 0, m, 10, 4, m, m, m, m, m }, // 2. 천안
{ m, m, 0, m, m, 21, m, 7, m, m }, // 3. 원주
{ m, 10, m, 0, 3, m, m, 10, m, m }, // 4. 대전
{ m, 4, m, 3, 0, m, 13, m, m, m }, // 5. 논산
{ m, m, 21, m, m, 0, m, m, m, 25 }, // 6. 강릉
{ m, m, m, m, 13, m, 0, m, 15, m }, // 7. 광주
{ m, m, 7, 10, m, m, m, 0, 9, 19 }, // 8. 대구
{ m, m, m, m, m, m, 15, 9, 0, 5 }, // 9. 부산
{ m, m, m, m, m, 25, m, 19, 5, 0 }, // 10. 포항
};
Scanner scan = new Scanner(System.in);
System.out.print("\n출발점을 문자로 입력하세요!! ex) \n");
for (int a = 0; a < array.length; a++) {
if (a > 0)
System.out.print(", ");
System.out.printf("%d.%s", (a + 1), array[a]);
}
System.out.print(" : ");
String str = scan.next();
for (int a = 0; a < array.length; a++) {
if (str.equals(array[a])) {
s = a + 1;
break;
}
}
for (int a = 0; a < data[s].length; a++) {
e = a + 1;
for (j = 0; j < 10; j++) {
v[j] = 0;
distance[j] = m;
}
distance[s - 1] = 0;
for (i = 0; i < 10; i++) {
min = m;
for (j = 0; j < 10; j++) {
if (v[j] == 0 && distance[j] < min) {
k = j;
min = distance[j];
}
}
v[k] = 1;
if (min == m)
break;
for (j = 0; j < 10; j++) {
if (distance[j] > distance[k] + data[k][j]) {
distance[j] = distance[k] + data[k][j];
via[j] = k;
}
}
}
System.out.printf("\n %s에서 출발하여, %s로 가는 최단 비용은 %d입니다.\n", array[s - 1], array[e - 1], distance[e - 1]);
int path[] = new int[10];
int path_cnt = 0;
k = e - 1;
while (true) {
path[path_cnt++] = k;
if (k == s - 1)
break;
k = via[k];
}
System.out.print(" 경로 : ");
for (i = path_cnt - 1; i >= 1; i--) {
System.out.printf("%d -> ", path[i] + 1);
}
System.out.printf("%d입니다.", path[i] + 1);
}
scan.close();
}
}
```
여기서는 모든 최단경로의 길이가 다 잘떴는데
첫번쨰꺼를 작업을 하다보니 꼬였습니다.....
이상 질문 마치겠습니다.
sehongpark님의 답변
## 초기값 설정
자기 자신에 대한 값이 안잡혀있는 것 같은데 한번 확인해 보시겠어요?
+ 서울 -> 서울 값이 0이 아닌 m인 이유가 있을까요?
```
String[] state = { "서울", "원주", "강릉", "천안", "논산", "대전", "대구", "포항", "광주", "부산" };
int[][] data = { { m, 15, m, 12, m, m, m, m, m, m }, // 서울
{ 15, m, 21, m, m, m, 7, m, m, m }, // 원주
{ m, 21, m, m, m, m, m, 8, m, m }, // 강릉
{ 12, m, m, m, 4, 10, m, m, m, m }, // 천안
{ m, m, m, 4, 3, m, m, m, 13, m }, // 논산
{ m, m, m, 10, 3, m, 10, m, m, m }, // 대전
{ m, 7, m, m, m, 10, m, 19, m, 9 }, // 대구
{ m, m, 25, m, m, m, 19, m, m, 5 }, // 포항
{ m, m, m, m, 13, m, m, m, m, 10 }, // 광주
{ m, m, m, m, m, m, 9, 5, 15, m } }; // 부산
```
wjdgus3562님의 답변
경로를 찾기전이라는 의미에서 0를 넣지는 않았는데 0을 넣어도 상관없을거 같아요
수정을 한후 계산식이 잘못된거같은데 도저히 모르겠습니다..
(배열 순서가 좀 바꼈습니다)
String[] array = { "서울", "천안", "원주", "대전", "논산", "강릉", "광주", "대구", "부산", "포항" };
int[][] data = { { 0, 12, 15, 0, 0, 0, 0, 0, 0, 0 }, // 1. 서울
{ 12, 0, 0, 10, 4, 0, 0, 0, 0, 0 }, // 2. 천안
{ 15, 0, 0, 0, 0, 21, 0, 7, 0, 0 }, // 3. 원주
{ 0, 10, 0, 0, 3, 0, 0, 10, 0, 0 }, // 4. 대전
{ 0, 4, 0, 3, 0, 0, 13, 0, 0, 0 }, // 5. 논산
{ 0, 0, 21, 0, 0, 0, 0, 0, 0, 25 }, // 6. 강릉
{ 0, 0, 0, 0, 13, 0, 0, 0, 15, 0 }, // 7. 광주
{ 0, 0, 7, 10, 0, 0, 0, 0, 9, 19 }, // 8. 대구
{ 0, 0, 0, 0, 0, 0, 15, 9, 0, 5 }, // 9. 부산
{ 0, 0, 0, 0, 0, 25, 0, 19, 5, 0 }, // 10. 포항
};
sehongpark님의 답변
네 코드를 전체적으로 돌려보고 확인을 좀 해봐야할거같은데.. 시간이 언제쯤 날지 모르겠네요 -0-;
1. 어떤 알고리즘으로 동작하는지 파악해야할 것이고,
2. 어떤 부분에서 버그가 생기는지 또한 알아봐야 하는데 말이죠 ㅠ
혹시 먼저 답을 찾으신다면 자답 하나 부탁드릴게용 저도 시간나는대로 확인해보겠습니당
wjdgus3562님의 답변
1. 다익스트라 알고리즘 입니다.
이거는 최단경로와 최소비용 구하는 알고리즘인데 이런기능을 추가하고싶습니다.
```
public void dijkstra(int v) //최소비용을 구하는 메소드
{
int[] check = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
distance[i] = Integer.MAX_VALUE;
check[i] = 0;
}
distance[v] = 0;
check[v] = 1;
for (int i = 1; i < n + 1; i++) {
if (check[i] == 0 && maps[v][i] != 0) {
distance[i] = maps[v][i];
}
}
for (int a = 0; a < n - 1; a++) {
int min = Integer.MAX_VALUE;
int min_index = -1;
for (int i = 1; i < n + 1; i++) {
if (check[i] == 0 && distance[i] != Integer.MAX_VALUE) {
if (distance[i] < min) {
min = distance[i];
min_index = i;
}
}
}
check[min_index] = 1;
for (int i = 1; i < n + 1; i++) {
if (check[i] == 0 && maps[min_index][i] != 0) {
if (distance[i] > distance[min_index] + maps[min_index][i]) {
distance[i] = distance[min_index] + maps[min_index][i];
ShortestPath[i] = min_index;
}
}
}
}
}
public void path(int EndNode, int StartNode) //최단 경로를 구하는 메소드
{
int Path[] = new int[1000];
int PathCount = 0;
int MiddleNode = EndNode;
while (true) {
Path[PathCount++] = MiddleNode;
if (MiddleNode == 0)
break;
MiddleNode = ShortestPath[MiddleNode];
}
System.out.print(" 경로 : " + StartNode + "->");
if (PathCount != 1) {
for (int i = PathCount - 2; i >= 1; i--) {
System.out.print(Path[i] + "->");
}
}
System.out.println(EndNode + " 최소 비용 : " + distance[EndNode]);
}
```
sehongpark님의 답변
## 참고 자료
+ 다익스트라 알고리즘 인접행렬 방식 (https://www.geeksforgeeks.org/java-program-for-dijkstras-algorithm-with-path-printing)
+ 다익스트라 알고리즘 집합 방식 (https://www.baeldung.com/java-dijkstra)
wjdgus3562님의 답변
답변해주신거에서 인터페이스를 추가하는순간 오류가 발생합니다.
이해는 하고있는데 제가 원하는노드수만큼 배열만큼 짜르면 오류가 나기 시작해서 수정이 힘듭니다. ㅠㅠ
sehongpark님의 답변
프로그램을 하나의 메소드에서 짜면 코드 수정이 힘듭니다 ㅠㅠ
1. 다음번엔 객체지향 개념도 적용하시구,
2. 메소드도 최대한 나누어서,
3. 변수도 의미있는 이름으로 작성해보길 권해드립니당
지금 코드 손보는중인데, 이거 햄버거 기프티콘 받아야겠는걸요? ㅎㅎ;;
wjdgus3562님의 답변
네 지금 저도 손코딩하는데 맞는거같으면서도 틀리는게 답답하네요 ㅠㅠ;;
기프티콘은 원하신다믄 바로보내드리겠습니당.
오늘까지 과제제출이라 죄송하지만 같이 화이팅 부탁드립니다.
sehongpark님의 답변
## 디테일 제외하고 얼추 되는 듯 합니다~~
```
import java.util.Scanner;
public class ShortestPath {
public static void main(String[] arg) {
int m = 5000;
int i, j, k = 0, s = 0, e = 0, min;
int[] v = new int[10];
int[] distance = new int[10];
int[] via = new int[10];
String[] array = { "서울", "천안", "원주", "대전", "논산", "강릉", "광주", "대구", "부산", "포항" };
// 1. 입력 받기
Scanner scan = new Scanner(System.in);
System.out.print("필요한 그래프의 노드 수를 입력하세요: ");
int n = scan.nextInt();
int[][] data = new int[n][n];
boolean isRight = false;
while (!isRight) {
// 2. 입력한 갯수 만큼 인접 행렬 기록.
// 1행: m 15 m
// 2행: 15 m 15
// 3행: m 21 m
for (int row = 0; row < n; row++) {
System.out.printf("\t%d행: ", row);
for (int col = 0; col < n; col++) {
data[row][col] = scan.nextInt();
}
}
System.out.println("\n\n=========== 입력 내용 =========");
// 3. 입력한 행을 확인
for (int row = 0; row < n; row++) {
System.out.printf("\t%d행: ", row);
for (int col = 0; col < n; col++) {
System.out.printf("%3d ", data[row][col]);
}
System.out.println();
}
System.out.printf("입력 사항이 맞습니까? [y/n]: ");
isRight = "y".equals(scan.next());
}
System.out.println("성공!");
System.out.print("\n출발 노드를 입력하시오. [ex: 대전] \n");
for (int a = 0; a < n; a++) {
if (a > 0)
System.out.print(", ");
System.out.printf("%s", array[a]);
}
System.out.print(" : ");
String str = scan.next();
for (int a = 0; a < n; a++) {
if (str.equals(array[a])) {
s = a + 1;
break;
}
}
for (int a = 0; a < data[s].length; a++) {
e = a + 1;
for (j = 0; j < 10; j++) {
v[j] = 0;
distance[j] = m;
}
distance[s - 1] = 0;
for (i = 0; i < 10; i++) {
min = m;
for (j = 0; j < 10; j++) {
if (v[j] == 0 && distance[j] < min) {
k = j;
min = distance[j];
}
}
v[k] = 1;
if (min == m)
break;
for (j = 0; j < n; j++) {
if (distance[j] > distance[k] + data[k][j]) {
distance[j] = distance[k] + data[k][j];
via[j] = k;
}
}
}
System.out.printf("\n %s에서 출발하여, %s로 가는 최단 비용은 %d입니다.\n", array[s - 1], array[e - 1], distance[e - 1]);
int path[] = new int[10];
int path_cnt = 0;
k = e - 1;
while (true) {
path[path_cnt++] = k;
if (k == s - 1)
break;
k = via[k];
}
System.out.print(" 경로 : ");
for (i = path_cnt - 1; i >= 1; i--) {
System.out.printf("%d -> ", path[i] + 1);
}
System.out.printf("%d입니다.", path[i] + 1);
}
scan.close();
}
}
```