전 글에서 말했듯 다음으로 다익스트라 알고리즘을 코드로 구현해보도록 하겠다.
다음은 다익스트라 알고리즘의 그래프가 될 가중치가 존재하는 그래프이다.
이 그래프 역시 인접행렬로 구현하기 위해 파일 데이터에 저장해주도록 하겠다.
가중치 그래프 역시 파일에서 하나씩 읽어와서 인접행로 구현하는 코드가 필요했고 코드는 다음과 같다.
private static void makeList2(String filename) {
int count = 1;
try (Scanner file = new Scanner(new File(filename))) {
while (file.hasNextLine()) {
String graphlength = file.nextLine();
Integer matrixlen = Integer.parseInt(graphlength);
int[][] adjWeight = new int[matrixlen][matrixlen];
for (int i = 0; i < matrixlen; i++) {
String datafield = file.nextLine();
String[] stringdata = datafield.split(" ");
int[] data = new int[stringdata.length];
for (int j = 0; j < stringdata.length; j++) {
data[j] = Integer.parseInt(stringdata[j]);
}
int coldata = data[0] - 1;
int[] rowdata = new int[(data.length - 1) / 2];
int[] weight = new int[(data.length - 1) / 2];
for (int j = 1; j < data.length; j++) {
if (j % 2 == 1) {
rowdata[j / 2] = data[j] - 1;
} else {
weight[j / 2 - 1] = data[j];
}
}
for (int j = 0; j < rowdata.length; j++) {
adjWeight[coldata][rowdata[j]] = weight[j];
}
}
for (int i = 0; i < adjWeight.length; i++) {
for (int j = 0; j < adjWeight.length; j++) {
if (i != j && adjWeight[i][j] == 0) {
adjWeight[i][j] = -1;
}
}
}
System.out.println("그래프" + "[" + count + "]");
System.out.println("-".repeat(33));
for (int i = 0; i < adjWeight.length; i++) {
for (int j = 0; j < adjWeight.length; j++) {
System.out.printf("%2d ", adjWeight[i][j]);
}
System.out.println();
}
System.out.println();
dijkstra(adjWeight, count);
System.out.println("=".repeat(33));
System.out.println();
count++;
}
} catch (FileNotFoundException e) {
System.out.println("파일 이름을 확인하세요.");
}
}
다음 코드를 실행 시키면 결과 값은 다음과 같다.
가중치 그래프에서 연결되어 있지 않은 부분은 무한대가 아닌 -1로 구현해 주었다. 또한 루프인 부분 즉 (1, 1), (2, 2), (3, 3) , (4, 4) 부분은 0으로 채워주었다.
다음은 dijkstra 알고리즘 코드이다.
private static void dijkstra(int[][] adjWeight, int count) {
int[][] root = new int[adjWeight.length][adjWeight.length];
root[0][0] = 1;
boolean[] ch = new boolean[adjWeight.length];
int[] d = new int[adjWeight.length];
for (int i = 1; i < adjWeight.length; i++) {
d[i] = Integer.MAX_VALUE;
}
ch[0] = true;
int k = 0;
for (int c = 0; c < adjWeight.length - 1; c++) {
int num = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < adjWeight.length; i++) {
if (d[i] > d[k] + adjWeight[k][i] && adjWeight[k][i] > 0 && !ch[i]) {
d[i] = d[k] + adjWeight[k][i];
root[i] = new int[adjWeight.length];
for (int j = 0; j < 5; j++) {
if (root[k][j] == 0) {
break;
}
root[i][j] = root[k][j];
}
}
if (min > d[i] && !ch[i]) {
min = d[i];
num = i;
}
}
ch[num] = true;
k = num;
for (int i = 0; i < adjWeight.length; i++) {
if (root[k][i] == 0) {
root[k][i] = k + 1;
break;
}
}
}
System.out.println("시작점: 1");
for (int i = 1; i < adjWeight.length; i++) {
System.out.print("정점 [" + (i + 1) + "]:");
for (int j = 0; j < adjWeight.length; j++) {
if (root[i][j] == 0) {
break;
}
if (j != 0) {
System.out.print(" -");
}
System.out.print(" " + root[i][j]);
}
System.out.println(", 길이: " + d[i]);
}
}
코드는 위와 같고 실행한 결과는 아래와 같다.
1에서 각각의 vertax에 도달할 수 있는 최단 경로를 구현한 결과이다.
이를 통해 최단경로 구현 문제 dijstra알고리즘을 풀 수 있었다. 다음코드는 작성하는데로 바로 업로드 하도록 하겠다.