다익스트라?
다익스트라는 양의 가중치를 가진 그래프들의 노드간 연결이 주어질때
시작점으로 부터 다른 모든 노드까지의 최소비용의 경로를 구한다.
특징
- 그리디(방문 하지 않은 노드중 최소 비용을 가지는 노드를 우선적으로 처리)
- DP(이미 계산한 최소 비용을 이용하여 그 노드를 경유하는 다른 노드의 최소비용을 계산)
- 임의의 두 노드간 경로가 최소 비용일때 그 경로를 이루는 부분 경로들도 모두 최소 비용으로 구성되어있다 (귀류법으로 증명)
- 시작점을 따라 일정한 속도로 흐르는 물을 생각하면 이해하기 쉽다(방문 배열로 구현)
- 가중치가 음일 경우 최소비용을 갱신하는 것이 어려워진다.
- 시간 복잡도는 우선순위 큐로 갱신 할때 O(ElogV)
최소 비용의 모든 경로 코드
public static void dijkstraWithTrack(int start, int target){
dist = new int[N];
vst = new boolean[N];
int[] track = new int[N]; // 경로를 저장할 배열
Arrays.fill(track,-1);
PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[0]-o2[0]);
pq.offer(new int[] {0,start});
Arrays.fill(dist,INF);
dist[start]=0;
while(!pq.isEmpty()){
int[] cur = pq.poll();
int curCost = cur[0], curNode = cur[1];
if(vst[curNode]) continue;
vst[curNode] = true;
for(int v=0; v<N; v++){
if(dist[v]>dist[curNode]+graph[curNode][v]){
dist[v] = dist[curNode]+ graph[curNode][v];
pq.offer(new int[] {dist[v],v}); // 갱신된 노드 넣기
// 일종의 linkedList;
track[v] = curNode; // 갱신된 노드의 이전 노드는 curNode이다.
}
}
}
System.out.println("from "+start+" vertex to "+target+" distance is "+dist[target]);
int idx = target;
System.out.print(idx+">");
while (idx>=0){
idx = track[idx];
if(idx == -1) break;
System.out.print(idx+">");
}
System.out.println();
}일종의 링크드리스트로 트랙 배열을 이용한다.
특정 노드까지의 비용을 구하는 dijkstra 코드
public static void preciseDijkstra(int start, int target){
dist = new int[N];
vst = new boolean[N];
int[] track = new int[N];
Arrays.fill(dist,INF);
Arrays.fill(track,-1);
PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[0]-o2[0]);
dist[start]=0;
pq.offer(new int[] {0,start});
int res=-1;
while(!pq.isEmpty()){
int[] cur = pq.poll();
int curCost = cur[0], curNode= cur[1];
if(curNode == target) {
res = curCost;
break;
}
if(vst[curNode]) continue;
vst[curNode] = true;
for (int v=0;v<N;v++){
if(dist[v]> dist[curNode]+graph[curNode][v]){
dist[v] = dist[curNode]+graph[curNode][v];
track[v] = curNode;
}
}
}
if(res ==-1) System.out.println("INFINITY");
else{
System.out.println("from "+start+" to "+target+" distance "+res);
int idx = target;
System.out.print(target+">");
while(idx>=0){
idx = track[idx];
if(idx == -1) break;
System.out.print(idx+">");
}
}
}전체코드
import java.io.*;
import java.util.StringTokenizer;
import java.util.PriorityQueue;
import java.util.Arrays;
class Main {
static int[][] data = {
// {a,b,c} == 노드 a에서 b까지 연결 되어있고 비용이 c로 연결
{0,1,50},
{0,2,30},
{1,3,30},
{1,4,70},
{2,3,20},
{2,4,40},
{3,4,10},
{3,5,80},
{4,5,30}
};
static int N=6,E=9; // vertex, edge 갯수
static int INF = 1004;
static int[][] graph = new int[N][N];
static int[] dist; // dijkstra의 파라미터로 호출 되는 시작노드를 기준으로 다른 노드까지의 최단 거리
static boolean[] vst; // 특정 노드 방문 했는지 체크
public static void main(String[] args) throws IOException{
// graph배열 (인접 행렬) 초기화
for (int i=0;i<N;i++){
for(int j=0; j<N; j++){
if(i ==j) graph[i][j] = 0; // 같은 노드는 출발값 0으로 설정
else graph[i][j]=INF;
}
}
//데이터에 따라 인접행렬 업데이트
for(int[] cur:data){
int a=cur[0],b=cur[1],c=cur[2];
graph[a][b] = c;
graph[b][a] = c;
}
dijkstra(1);
dijkstraWithTrack(1,5);
preciseDijkstra(1,5);
}
public static void dijkstra(int start){
dist = new int[N];
vst = new boolean[N];
PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[0]-o2[0]);
pq.offer(new int[] {0,start});
for(int i=0; i<N; i++) dist[i] = INF;
dist[start] = 0;
while(!pq.isEmpty()){
int[] cur = pq.poll();
int curNode = cur[1], curCost = cur[0];
if(vst[curNode]) continue; // 이미 처리된 경우 통과;
vst[curNode] = true;
for(int v=0; v<N; ++v){
if(dist[v] > dist[curNode]+graph[curNode][v]){
// 현재 노드를 거쳐서 가는 경우가 더 비용이 낮은 경우 그렇게 dist를 갱신한다.
dist[v] = dist[curNode]+graph[curNode][v];
pq.offer(new int[] {dist[v],v});
}
}
}
System.out.println("simple dijkstra: start from \'"+start+"\'vertex");
for (int i=0; i<N; i++) System.out.print("to vertex "+i+" cost: "+dist[i]+" ");
System.out.println();
}
// 최단거리까지의 경로를 기록함
public static void dijkstraWithTrack(int start, int target){
dist = new int[N];
vst = new boolean[N];
int[] track = new int[N]; // 경로를 저장할 배열
Arrays.fill(track,-1);
PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[0]-o2[0]);
pq.offer(new int[] {0,start});
Arrays.fill(dist,INF);
dist[start]=0;
while(!pq.isEmpty()){
int[] cur = pq.poll();
int curCost = cur[0], curNode = cur[1];
if(vst[curNode]) continue;
vst[curNode] = true;
for(int v=0; v<N; v++){
if(dist[v]>dist[curNode]+graph[curNode][v]){
dist[v] = dist[curNode]+ graph[curNode][v];
pq.offer(new int[] {dist[v],v}); // 갱신된 노드 넣기
// 일종의 linkedList;
track[v] = curNode; // 갱신된 노드의 이전 노드는 curNode이다.
}
}
}
System.out.println("from "+start+" vertex to "+target+" distance is "+dist[target]);
int idx = target;
System.out.print(idx+">");
while (idx>=0){
idx = track[idx];
if(idx == -1) break;
System.out.print(idx+">");
}
System.out.println();
}
public static void preciseDijkstra(int start, int target){
dist = new int[N];
vst = new boolean[N];
int[] track = new int[N];
Arrays.fill(dist,INF);
Arrays.fill(track,-1);
PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[0]-o2[0]);
dist[start]=0;
pq.offer(new int[] {0,start});
int res=-1;
while(!pq.isEmpty()){
int[] cur = pq.poll();
int curCost = cur[0], curNode= cur[1];
if(curNode == target) {
res = curCost;
break;
}
if(vst[curNode]) continue;
vst[curNode] = true;
for (int v=0;v<N;v++){
if(dist[v]> dist[curNode]+graph[curNode][v]){
dist[v] = dist[curNode]+graph[curNode][v];
track[v] = curNode;
}
}
}
if(res ==-1) System.out.println("INFINITY");
else{
System.out.println("from "+start+" to "+target+" distance "+res);
int idx = target;
System.out.print(target+">");
while(idx>=0){
idx = track[idx];
if(idx == -1) break;
System.out.print(idx+">");
}
}
}
}
Pragmatic, Productive, Positivist