[알고리즘] 동적프로그래밍 Part 2 - Floyd 구현 - by Java

import java.util.*;

public class floyd {

private int D[][];

private int W[][];

private int P[][];

// 생성자

floyd(int n){

int i,j;

Scanner scanner = new Scanner(System.in);

// 받은 종점의 개수만큼 배열을 생성한다.

D = new int[n][n];  // D는 최단거리를 저장하는 변수 

W = new int[n][n];  // W는 가중치변수

P = new int[n][n];  // P는 이동간 거쳐가는 곳을 알려주기 위해 있는 변수

for ( i = 0 ; i < n ; i++ )

for ( j = 0 ; j < n ; j++ ){

System.out.print("종점 " + ( i+1 ) + "에서 종점 " + ( j+1 ) + "로 가는 길의 가중치를 입력해주세요 :  ");

W[i][j] = scanner.nextInt();

P[i][j] = 0;

}

D = W;

}

// getter

public int[][] getD() { return D; }

public int[][] getW() { return W; }

public int[][] getP() { return P; }

// 최단 경로의 길이와 그 경로를 가는 동안 거쳐가는 종점을 구하는 함수

public void floyding ( int n, int[][] W, int [][] D, int[][] P){

int i, j, k;

for ( k = 0 ; k < n ; k++ )

for ( i = 0 ; i < n ; i++)

for ( j = 0 ; j < n ; j++ )

if ( D[i][k]+D[k][j] < D[i][j] ){

D[i][j] = D[i][k]+D[k][j];

P[i][j] = k;

}

}

// i에서 j로 가기 위해 거쳐가는 노드

public void path(int i, int j){

if ( P[i][j] != 0 ){

path(i,P[i][j]);

System.out.println((P[i][j] + 1 ) + "Node");

path(P[i][j],j);

}

}

public static void main(String[] args){

int n; // 정점의 개수를 받는 변수

int [][]tempD; // D변수 임시 저장

int from, to;   // 어디서 어디로 갈것인가?

floyd f; // floyd클래스 객체

Scanner scanner = new Scanner(System.in);

n = scanner.nextInt();

f = new floyd(n);

f.floyding(n, f.getW(),f.getD(), f.getP()); 

tempD = new int[n][n];

tempD = f.getD();

System.out.println("출발점과 도착점을 적어줒세요.");

from = scanner.nextInt();

to = scanner.nextInt();

System.out.println("최단경로 비용 : " + tempD[from-1][to-1]);

                // path함수는 사이에있는(L에속하는) 종점만 보여주므로 시작과 끝을 찍어주어 출력이 이쁘게한다. 

System.out.println(from + "node");

f.path(from-1,to-1);

System.out.println(to + "node");

/* test

for ( int i = 0 ; i < n ; i++ ){

for ( int  j = 0 ; j < n ; j++ )

System.out.print(tempD[i][j] + " ");

System.out.println();

}

*/

}

}

소스에 주석을 살펴봐도 알기 쉬울 것이다.
중간에   void floyding ( int n, int[][] W, int [][] D, int[][] P) 함수에서는 W,D,P를 불러오지 않아도 되지만
다른 클래스에서 생성된것을 처리한다고 가정을 하기 위해서 위와 같이 구현하였다. 매개변수를 줄여도 무관하다.
또한, 중간중간에 -1과 +1등이 되어있는 것은 index를 0이 아닌 1부터 사용하기 위해서 사용된것이다. 

개인적으로 C를 좋아하고 제약이 없는 것은 C로 짜지만... 교수님이 자바를 좋아하셔서 자바로했다.