public class Dijkstra {
private int[][] w; // 가중치 행렬
private int length[]; // 시작점에서 각 정점으로 가는 최소값을 저장하는 곳
private int touch[]; // 출발점에서 목적지까지 가는데 걸리는 최소 가중치
private boolean isSelect[]; // 정점이 선택되었는지를 판별하기 위한 것
private char vertex[]; // 숫자로 한계산을 영어로 치환하기 위한 것
private int n; // 정점들의 수
// 정점의 개수를 받아서 그 만큼 할당을 해주면서 초기화하는게 옳은 것
// 다른 부분은 그렇게했지만 가중치 받는 것은 문제에서 가중치가 주어졌기때문에
// -> 고정되어서 입력없이 바로 입력되게하였다.
Dijkstra(int n){
this.n = n;
w = new int[n][n];
length = new int[n];
touch = new int[n];
vertex = new char[n];
isSelect = new boolean[n];
// 일반시 n만큼 loop을 돌면서 값을 받을 변수들 vertex 이름을 결정후
// 이름에서 이름으로 가는 값을 받는다. 연결되지 않는 간선에 대해선 INF가 맞지만
// 편의상 99로 넣었다.
vertex = new char[]{'a','b','c','d','e','f'};
w = new int[][]{
{ 0, 1, 2, 5, 99, 99},
{99, 0, 2, 3, 99, 99},
{99, 99, 0, 1, 4, 7},
{99, 99, 99, 0, 3, 6},
{99, 99, 99, 99, 0, 2},
{99, 99, 99, 99, 99, 0}
}; // 99 is INF
}
public void dijkstra(){
int vnear = 0; // 새로 선택된 정점의 번호의 임시저장소
isSelect[0] = true; // 0 : 출발 정점
for ( int i = 1 ; i < n ; i++ ){
isSelect[i] = false;
touch[i] = 0;
length[i] = w[0][i]; // 0과 다른 정점이 직접적으로 연결된 값 저장
}
// 다음 노드 후보를 검색한다.
for ( int i = 0 ; i < n-1 ; i++ ){
int minval = 99; // minval = INF
for ( int j = 0 ; j < n ; j++ ){
if ( !isSelect[j] ){
if ( length[j] < minval) {
minval = length[j];
vnear = j;
}
}
}
isSelect[vnear] = true; //후보를 선택해준다.
// 연결되는 정점을 추가적으로 출력해준다.
System.out.println("간선 V(" + (vertex[touch[vnear]]) + "," + vertex[vnear] +")선택");
// 추가된 정점을 포함하여 새롭게 최단거리를 계산한다.
for ( int j = 0 ; j < n ; j++ ){
if ( !isSelect[j] ){
if ( length[vnear] + w[vnear][j] < length[j]){
length[j] = length[vnear] + w[vnear][j];
touch[j] = vnear;
}
}
}
}
}
public static void main(String args[]){
Dijkstra d = new Dijkstra(6); // 사용자 입력없이 바로 문제를 풀기위해 정의 되있으므로...
System.out.println("최단경로 신장트리를 이루기 위해 연결된 간선");
d.dijkstra();
}
}