반응형
메인 클래스는 알아서 만들어서 쓰면 된다.
개선 방법은 쓰지 않음.
다익스트라
예를 들어, 0에서 가장 가까운 곳은 5번 노드(거리1)이다.
그럼 5번 노드가 vnear이 되고
5번 노드를 경유해서 가는 루트를 고려하여 최소길이를 갱신
(이전가지는 0에서 바로 가는 루트들이 최소인 것이다)
그 다음 5번 노드는 제외하고 다음으로 가까운 곳은 1번 노드이니
1번 노드가 vnear이 되고
아까 5번 노드를 경유한 루트도 고려하여 갱신된 최소 루트들을
1번 노드를 경유하는 것도 고려하여 또다시 갱신
이와 같은 방법으로 마지막 노드까지 반복
벨만 포드
시작점 고정시키고
경유지랑 목적지를 이중 반복문 돌려서
경유한 길이와 원래 길이를 비교해서 짧은 것으로 갱신
갱신할 때 마다 길이값들이 달라지므로 다시 비교가 필요함
따라서 더이상 갱신이 없을 때까지 계속 반복
import java.util.Random;
import java.util.*;
public class Routing_Algorithms {
private int m_size;
private int m_cost[][];
public Stack<Integer> v_route = new Stack<Integer>();
// 생성자1: 수동으로 입력(매트릭스 크기와 노드 간 cost를 인자로 받는다)
Routing_Algorithms(int size, int cost[][]) {
m_size = size;
m_cost = cost;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (m_cost[i][j] == 999)
System.out.print("- ");
else
System.out.print(m_cost[i][j] + " ");
}
System.out.println();
}
System.out.println();
};
// 생성자2: 사이즈만 받고, 랜덤으로 대칭행렬 랜덤 생성 구현
Routing_Algorithms(int size) {
m_size = size;
Random random = new Random();
int mat[][] = new int[size][size]; // 매트릭스 생성. default 값인 0으로 초기화 됨
// 초기화
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i == j)
mat[i][j] = 0; // 대각선 성분은 0으로 초기화
else
mat[i][j] = 999; // 나머지는 999로 초기화
}
}
// 랜덤 디그리 (직접 연결되어 있는 노드의 수, size제곱의 반 정도로 설정, 대칭행렬인걸 주의)
for (int i = 0; i < (int) Math.pow(size-1, 2) / 3; i++) {
int row = random.nextInt(size); // 행: 0 ~ size-1 사이의 난수 생성
int col = random.nextInt(size); // 열: 0 ~ size-1 사이의 난수 생성
// 이미 코스트가 부여된 곳이거나(그럼 999가 아니다.) 대각선 상에 있는 곳이면(0이니까 999가 아니다) 다시 뽑기
if (mat[row][col] != 999) {
i--;
continue;
}
// 랜덤 코스트
mat[row][col] = random.nextInt(7) + 1; // 1~7 사이의 난수 생성
mat[col][row] = mat[row][col]; // 대칭 성분에도 똑같은 값 대입(대칭 행렬일 경우)
}
m_cost = mat;
// 매트릭스 출력
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (mat[i][j] == 999)
System.out.print("- ");
else
System.out.print(mat[i][j] + " ");
}
System.out.println("");
}
System.out.println();
}
// 다익스트라 알고리즘
public void RunDijkstra() {
long start = System.currentTimeMillis(); // 프로그램 시작 시간
System.out.println("↓↓↓↓↓↓다익스트라 알고리즘↓↓↓↓↓↓\n");
int parent[] = new int[m_size]; // 0~i 경로 상 목적지인 i노드의 바로 전 노드 (경유지)
int length[] = new int[m_size]; // 0~i 까지의 cost
int lengthSave[] = new int[m_size]; // 출력을 위해 길이를 저장할 배열
boolean connected = true;
// 초기화
for (int i = 0; i < m_size; i++) {
parent[i] = 0;
length[i] = m_cost[0][i];
}
for (int i = 0; i < m_size - 1; i++) { // 시작점을 제외한 나머지 점 만큼 돈다는 뜻
int min = 999;
int vnear = 0; //가장 가까운 점, 새로 추가되는 점
// 가장 가까운 점 찾기(출발지에서 부터 가장 가까운 점, 아직 닿지 않는 곳은 무한대이고, 이미 나왔던 건 아래에서 -1로 만들어서 안 걸리도록 함)
for (int j = 1; j < m_size; j++) {
if (length[j] < min && length[j] > 0) {
min = length[j];
vnear = j;
}
}
lengthSave[vnear] = length[vnear]; // 거리는 출력할 때 필요하니까 백업
// 길이 갱신 (점(vnear)이 추가 되었으니 각 점까지의 루트가 바뀔 수 있다. 추가된 점을 거쳐 가는게 더 짧으면 갱신하고, 아니면 그냥 둔다)
for (int j = 1; j < m_size; j++) {
// (출발지 ~ 가장 가까운 점) + (가장 가까운 점 ~ j) 가 기존의 (출발지 ~ j)의 거리보다 짧다면 갱신
if (length[vnear] + m_cost[vnear][j] < length[j]) {
length[j] = length[vnear] + m_cost[vnear][j];
parent[j] = vnear; // 루트가 바로 j로 가는 거에서 vnear을 경유하는걸로 바뀌었으니, 경유지도 갱신한다.
}
}
length[vnear] = -1; // 다음 반복 때 다시 걸리지 않도록 -1로 만들어준다.
}
// 출력
for(int i=1; i<m_size; i++) {
// 목적지 출력
System.out.print("[목적지]: " + i + "\t\t");
// 거리 출력
System.out.print("[거리]: " + lengthSave[i] + "\t\t");
// 경로 출력 (스택 이용)
System.out.print("[경로]: ");
for(int j=i; j!=0; j=parent[j]) {
v_route.push(parent[j]);
}
while(!v_route.isEmpty()) {
System.out.print(v_route.pop() + " - ");
}
System.out.println(i + "\n");
}
long end = System.currentTimeMillis(); // 프로그램 종료 시간
System.out.println("[소요시간]: " + (end-start)+" milliseconds\n");
}
// 벨만 포드 알고리즘 (대칭행렬로 하면 무한 반복 돌 수 있음 주의)
public void RunBellmanFord() {
long start = System.currentTimeMillis(); // 프로그램 시작 시간
System.out.println("↓↓↓↓↓↓벨만 포드 알고리즘↓↓↓↓↓↓\n");
int parent[] = new int[m_size]; // 출발지에서 목적지까지의 경로 상에서 목적지의 바로 전 노드 (경유지)
int length[] = new int[m_size]; // 출발지에서 목적지까지의 총 거리
boolean connected = false;
// 초기화
for (int i = 0; i < m_size; i++) {
parent[i] = 0;
length[i] = m_cost[0][i];
}
// 계산
boolean update = true;
while(update) { //더 이상 변경점이 없을 때까지 반복
update = false;
// 시작점에서 각 점까지 최단 거리 구하기
for(int i=1; i<m_size; i++) { //경유지
for(int j=1; j<m_size; j++){ //목적지
if(length[j] > length[i] + m_cost[i][j]) { //경유해서 가는게 빠르면 거리와 경유지를 갱신
length[j] = length[i] + m_cost[i][j];
parent[j] = i;
update = true;
}
}
}
}
// 출력
for(int i=1; i<m_size; i++) {
// 목적지 출력
System.out.print("[목적지]: " + i + "\t\t");
// 거리 출력
System.out.print("[거리]: " + length[i] + "\t\t");
// 경로 출력 (스택 이용)
System.out.print("[경로]: ");
for(int j=i; j!=0; j=parent[j]) {
v_route.push(parent[j]);
}
while(!v_route.isEmpty()) {
System.out.print(v_route.pop() + " - ");
}
System.out.println(i + "\n");
}
long end = System.currentTimeMillis(); // 프로그램 종료 시간
System.out.println("[소요시간]: " + (end-start)+" milliseconds\n");
}
}
반응형