고민의 흔적

플로이드-위셜

그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 음수 가중치가 있어도 수행할 수 있고, 동적 계획법의 원리를 이용해 알고리즘에 접근한다.

시간 복잡도(노드수 : V)

O(V^3)

플로이드-위셜 핵심 이론

플로이드-위셜 알고리즘을 도출하는 가장 핵심적인 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다.

플로이드 위셜 점화식

D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

1. 배열을 선언하고 초기화하기

D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 배열이라 정의한다. S와 E의 값이 같은 같은 0, 다른 칸은 무한으로 초기화한다. 여기에서 S==E 는 자기 자신에게 가는 데 걸리는 최단 경로값을 의미하기 때문이다.

2. 최단 거리 배열에 그래프 데이터 저장하기

출발 노드는 S, 도착 노드는 E, 이 에지의 가중치는 W라고 했을 때 D[S][E] = W로 에지의 정보를 배열에 입력한다. 이로써 플로이드-위셜 알고리즘은 그래프를 인접 행렬로 표현한다는 것을 알 수 있다.

3. 점화식으로 배열 업데이트하기

기존에 구했던 점화식을 3중 for문 형태로 반복하면서 배열의 값을 업데이트한다.

플로이드-위셜 알고리즘 로직

for 경유지 K에 관해 (1 ~ N)

   for 출발 노드 S에 관해 (1 ~ N)

      for 도착 노드 E에 관해 (1 ~ N)

        D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 

플로이드-위셜 알고리즘은 모든 노드 간의 최단 거리를 확인해 주기 때문에 시간 복잡도가 빠르지 않은 편이다. 플로이드-위셜 알고리즘을 사용해야 하는 문제가 나오면 일반적으로 노드의 개수의 범위가 다른 그래프에 적게 나타난다는 것을 알 수 있다.

코드로 표현

static int N,M;
static int distance[][];

distance = new int[n + 1][n + 1];

for(int i = 1; i <= N; i++) { // 인접 행렬 초기화
	for(int j = 1; j <= N; j++) {
    	if(i == j) {
        	distance[i][j] = 0;
        }
        else {
        	distance[i][j] = 1000001; // 충분히 큰 수로 저장
        }
    }
}
for(int i = 0; i < M; i++) {
	int s, e, v 입력받기
    if(distance[s][e] > v) {
    	distance[s][e] = v;
    }
}
for(int k = 1; k <= N; k++) { // 플로이드-위셜 알고리즘 수행하기
	for(int i = 1; i <= N; i++) {
    	for(int j = 1; j <= N; j++) {
        	if(distance[i][j] > distance[i][k] + distance[k][j])
            	distance[i][j] = distance[i][k] + distance[k][j];
            }
        }
    }
}
출력 부분

69번 문자열 집합

내가 떠올린 풀이 해설

집합 S에 속해있는 단어들을 이용해 트라이 구조를 생성하고, 트라이 검색을 이용해 문자열 M개의 포함 여부를 카운트하는 전형적인 트라이 자료구조 문제이다. 트라이 자료구조를 생성하고 현재 문자열을 가리키는 위치의 노드가 공백 상태라면 신규 노드를 생성하고 아니라면 이동한다. 문자열 마지막에 도달하면 리프 노드라고 표시한다. 트라이 자료구조 검색으로 집합 S에 포함된 문자열을 센다. 부모-자식 관계를 이용해 대상 문자열을 검색했을 때 문자열이 끝날 때까지 공백 상태가 없고, 현재 문자의 마지막 노드가 트라이의 리프 노드라면 이 문자를 집합 S에 포함된 문자열로 센다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek14425 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		dNode root = new dNode();
		while(n > 0) { // 트라이 자료구조 구축하기 
			String text = br.readLine();
			dNode now = root;
			for(int i = 0; i < text.length(); i++) {
				char c = text.charAt(i);
				// 26개 알파벳의 위치를 배열 index로 나타내기 위해 -'a' 수행하기 
				if(now.next[c - 'a'] == null) {
					now.next[c - 'a'] = new dNode();
 				}
				now = now.next[c - 'a'];
				if(i == text.length() - 1) {
					now.isEnd = true;
				}
			}
			n--;
		}
		int count = 0;
		while(m > 0) {    // 트라이 자료구조 검색하기 
			String text = br.readLine();
			dNode now = root;
			for(int i = 0; i < text.length(); i++) {
				char c = text.charAt(i);
				if(now.next[c - 'a'] == null) { // 공백 노드라면 이 문자열을 포함하지 않음 
					break;
				}
				now = now.next[c - 'a'];
				if(i == text.length() - 1 && now.isEnd) { // 문자열의 끝이고 현재까지 모두 일치하면 
					count++;   // S 집합에 포함되는 문자열 
				}
			}
			m--;
		}
		System.out.println(count);
	}

}
class dNode {
	dNode[] next = new dNode[26];
	boolean isEnd;  // 문자열의 마지막 유무를 표시하기 
}

오늘의 회고

오늘은 트라이 자료구조를 배우고 트라이 문제를 풀었습니다. 1문제 밖에 풀지 못했습니다. 장마라 밖에 비도 많이 오고 날씨도 우중충한데 퍼지지 않고 공부하겠습니다.

Docker 컨테이너가 사용하는 스토리지

1. 도커의 레이어 기술

도커의 컨테이너 이미지는 ReadOnly 상태입니다. 컨테이너에 추가되는 데이터들은 별도의 ReadWrite레이어에 저장됩니다. 도커 컨테이너를 실행시키면 ReadOnly와 ReadWrite를 만들어서 같이 실행되어 하나의 프로세스가 되어서 동작을 합니다. 어떻게 ReadOnly와 ReadWrite가 하나인 것처럼 보일까요? 이것은 도커가 가지고 있는 레이어의 기술입니다. 이 레이어 기술을 유니온 파일 시스템 또는 overlay라고 합니다. 기존에 가지고 있던 ReadOnly 레이어에서 ReadWrite 레이어에 변경사항이 마치 하나인 것처럼 보여주는 것입니다. 도커에서는 컨테이너를 실수로 삭제하면 그 안에 있던 데이터가 다 날아갑니다. 이를 보안하기 위해 -v volume 명령어를 사용합니다.

2. volume 명령어

volume 옵션
-v <host path>:<container mount path>

-v <host path>:<container mount path>:<read writer mode>

-v <container mount path>

$ docker run -d --name db -v /data:/var/lib/mysql -e MYSQL_ROOT_PASSWORD=pass mysql:latest
데이터를 실제 호스트에 기록되게 볼륨 마운트하면 보안 이슈가 있다. 
해커가 파일을 저장하게되면 호스트에도 저장된다.

$ docker run -d --name db -v /data:/var/www/html:ro httpd
위의 보안 문제를 해결하기 위해 둘째 라인처럼 ro :readonly을 써준다.

$ docker run -d --name db -v /var/lib/mysql -e MYSQL_ROOT_PASSWORD=pass mysql:latest
-v 뒤에 호스트 주소가 없으면 data 디렉토리 처럼 uuid로 된 디렉토리를 만들고 
그 밑에 data디렉토리를 만들어서 거기에 저장된다.

3. 컨테이너끼리 데이터 공유하기

컨테이너와 컨테이너끼리 데이터 마운트로 데이터 공유가 가능합니다.

이를 이용하면 리눅스 컨테이너가 /webdata와 마운트 되어있고 index.html을 만들었고 nginx 컨테이너가 같은 폴더를 마운트하고 있으면 유저에게 index.html을 보여줄 수 있습니다. 또한 리눅스에서 index.html 파일을 변경하여도 적용됩니다.

4. volume 실습

docker exec -it db /bin/bash

위에 명령어는 도커에서 mysql에 접속하는 명령어입니다.

성공적으로 mysql에 접속한 것을 확인하실 수 있습니다. hs 라는 이름으로 database를 만들었습니다.

동작중인 컨테이너를 삭제하여도 호스트의 dbdata 디렉터리에는 hs 가 남아있는 것을 확인하실 수 있습니다.

-v 옵션에 host 디렉토리의 이름을 지정해주지 않았습니다.

docker inspect 명령어로 host 디렉토리의 이름을 지정하지 않으면 어느 디렉터리로 Mount 되는지 확인하였습니다.

host 디렉토리를 지정하지 않으면 /var/lib/docker/volumes/에 uuid로 디렉터리가 만들어지고 그 밑에 _data라는 디렉터리가 만들어진 것을 확인하실 수 있습니다.

따배도 강의를 보고 실습을 하다가 발생하는 오류를 작성했습니다.

1. no matching manifest 오류

MySQL을 실행시키려고 명령어를 작성하였는데 no matching manifest 오류가 발생하였습니다.

해결 방법은 간단했습니다. 실행시킬 때 플랫폼 주소도 함께 작성해주면 해결됩니다.

docker run --platform linux/amd64 -d --name db -v /data:/var/lib/mysql -e MYSQL_ROOT_PASSWORD=pass mysql:latest

성공적으로 실행이 되는가 했는데 이번에는 Mounts denied 오류가 발생하였습니다.

2. Mounts denied 오류

우선 docker desktop 화면에서 오른쪽 상단에 보시면 Settings에 톱니바퀴의 이미지가 있습니다. 클릭합니다.

Settings를 클릭하시면 위와 같은 화면이 나오실 텐데 위에 화면에서 Resources에서 FILE SHARING을 클릭해 줍니다.

그 화면에서 마운트를 진행할 폴더를 설정해줍니다. 설정하시고 오른쪽 하단에 Apply&Restart 버튼을 눌러줍니다.

다시 MySQL을 Run하시면 정상적으로 동작하는 것을 확인하실 수 있습니다.

67번 트리의 부모 찾기

내가 떠올린 풀이 해설

인접 리스트 자료구조를 사용하면 간편하게 데이터를 저장할 수 있다. 트리의 루트가 1이라고 지정돼 있기 때문에 1번 노드부터 DFS로 탐색하면서 부모 노드를 찾아 주면 문제를 쉽게 풀 수 있다. 출력은 정답 배열의 2번 인덱스부터 값을 차례대로 출력한다.

정확한 풀이

import java.io.*;
import java.util.*;

public class Baek11725 {
	static ArrayList<Integer>[] arr;
	static int[] answer;
	static boolean[] visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[n + 1];
		visit = new boolean[n + 1];
		answer = new int[n + 1];
		
		for(int i = 0; i <= n; i++) {
			arr[i] = new ArrayList<>();
		}
		
		for(int i = 1; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			arr[s].add(e);
			arr[e].add(s);
		}
		DFS(1);
		for(int i = 2; i <= n; i++) {
			System.out.println(answer[i]);
		}
	}
	private static void DFS(int i) {
		visit[i] = true;
		for(int k : arr[i]) {
			if(!visit[k]) {
				answer[k] = i;
				DFS(k);
			}
		}
	}
}

68번 트리

내가 떠올린 풀이 해설

이 문제의 핵심은 리프 노드를 어떻게 제거하는지 이다. 리프 노드를 탐색하는 탐색 알고리즘을 수행할 때나 제거하는 노드가 나왔을 때 탐색을 종료하는 아이디어를 적용하면 실제 리프 노드를 제거하는 효과를 낼 수 있다. 인접 리스트로 트리 데이터를 구현한다. DFS를 탐색하면서 리프 노드의 개수를 센다. 제거 대상 노드를 만났을 때 그 아래 자식 노드들과 관련된 탐색은 중지한다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1068 {
	static ArrayList<Integer>[] arr;
	static boolean[] visit;
	static int r;
	static int answer;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[n];
		visit = new boolean[n];
		
		for(int i = 0; i < n; i++) {
			arr[i] = new ArrayList<>();
		}
		int root = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			int s = Integer.parseInt(st.nextToken());
			if(s != -1) {
				arr[s].add(i);
				arr[i].add(s);
			}
			else {
				root = i;
			}
		}
		r = Integer.parseInt(br.readLine());
		if(r == root) {
			System.out.println(0);
		}
		else {
			DFS(root);
			System.out.println(answer);
		}
	}
	private static void DFS(int root) {
		visit[root] = true;
		int c = 0;
		for(int v : arr[root]) {
			if(!visit[v] && v != r) { // 삭제 노드가 아닐 떼도 탐색 중지 
				c++;
				DFS(v);
			}
		}
		if(c == 0) {
			answer++; // 자식 노드가 아닐 때 리프 노드로 간주하고 정답값 증가 
		}
	}
}

오늘의 회고

오늘은 트리와 관련된 문제 2문제를 풀었습니다. 알고리즘 개념에 대해 복습하는 시간을 가지면서 초반보다 문제를 푸는 개수가 많이 줄어들어 시간도 부족하고 알고리즘을 끝낼 수 있을까란 조바심도 들지만 천천히 조바심 가지지 않고 완전히 내 것으로 만들면서 나아가겠습니다.

컨테이너 리소스 제한 명령어

docker command 를 통해 제한할 수 있는 리소스는 

1. CPU
2. Memory
3. Disk I/O 가 있다.

1.  Memory 리소스 제한

Memory 리소스 제한
  제한 단위는 b, k, m, g로 할당
--memory, -m : 컨테이너가 사용할 최대 메모리 양을 지정

--memory-swap : 컨테이너가 사용할 스왑 메모리 영역에 대한 설정

--memory-reservation : --memory 값보다 적은 값으로 구성하는 소프트 제한 값 설정

--oom-kill-disable : OOM Killer가 프로세스 kill 하지 못하도록 보호

$ docker run -d -m 512m nginx

$ docker run -d -m 1g --memory-reservation 500m nginx
: --memory-reservation 1g 메모리를 지정하는데 최소 500메가까지 보장 받는다.

$ docker run -d -m 200m --memory-swap 300m nginx
: swap은 메모리가 200m swap이 300m일 때 swap은 300 - 200으로 swap의 용량은 100m이다.

$ docker run -d -m 200m --oom-kill-disable nginx
: oom-kill 실제 피지컬 메모리가 부족해도 nginx는 죽이지 마라

리눅스에서 부하테스트를 하기위해 dockerfile을 작성했다.

dockerfile을 build하는 모습이다.

부하 테스트를 진행하는 사진입니다.

메모리를 100m를 설정을하고 swap도 100m로 설정을해서 실제로 swap에는 메모리가 없습니다.

5초동안 90m 부하를 일으키는 테스트를 진행했습니다..

정상적으로 실행 되고 있습니다.

5초동안 150m를 진행하였는데 실패하는 화면입니다. 

2. CPU 리소스 제한

CPU 리소스 제한
--cpus : 컨테이너에 할당할 CPU core 수를 지정

--cpuset-cpus : 컨테이너가 사용할 수 있는 CPU나 코어를 할당. cpu index는 0부터

--cpu-share : 컨테이너가 사용하는 CPU 비중을 1024값을 기반으로 설정



$ docker run -d --cpus=".5" ubuntu
: .5는 예를 들어 cpu 4개중에 1개를 절반까지 쓸수 있다.

$ docker run -d --cpu-shares 2048 ubuntu
: 디폴트는 1024인데 2048로 설정하면 다른 cpu보다 더 많은 리소스를 할당한다.

$ docker run -d --cpuset-cpus 0-3 ubuntu

3. Block I/O 제한

Block I/O 제한
--blkio-weight : Block IO의 Quota를 설정할 수 있으며 100 ~ 1000까지 선택 default 500
--blkio-weight-device : weight-device는 weight값을 한 device에만 적용시킨다.

--device-read-bps : 특정 디바이스에 대한 읽기와 쓰기 작업의 초당 제한을 kb, mb, gb단위로 설정
--device-write-bps 

--device-read-iops : 컨테이너의 read/write 속도의 쿼터를 설정한다. 초당 quota를 제한해서 I/O를 발생시킴
--device-write-iops :  0이상의 정수로 표기 초당 데이터 전송량 = IOPS * 블럭크기

4. 모니터링

docker stat m4

실행중인 컨테이너의 런타임 통계를 확인하는 명령어이다.

docker events -f container=name
docker image -f container=name

도커 호스트의 실시간 event 정보를 수집해서 출력하는 명령어이다.

cAdvisor이라는 모니터링툴이 있는데 제 맥북 환경에서 실행이 안되어서 모니터링을 못했습니다.

https://github.com/google/cadvisor

벨만-포드

벨만-포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 탐색한다. 음수 가중치 에지가 있어도 수행할 수 있다. 또한 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.

시간 복잡도(노드 수 : V, 에지 수 : E)

O(VE)

벨만-포드 알고리즘 핵심 이론

1. 에지 리스트로 그래프 구현하고 최단 경로 배열 초기화하기

   벨만-포드 알고리즘은 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현한다. 또한 최단 경로 배열은 출발 노드는 0, 나머지 노드는 무한대로 초기화한다. 

2. 모든 에지를 확인해 정답 배열 업데이트하기

   최단 거리 배열에서 업데이트 반복 횟수는 노드 개수 -1입니다. 노드 개수가 N이고, 음수 사이클이 없을 때 특정 노드 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N-1이기 때문이다. 특정 에지 E = (s, e, w)에서 다음 조건을 만족하면 업데이트를 실행한다.

3. 음수 사이클 유무 확인하기

   음수 사이클 유무를 확인하기 위해 모든 에지를 한 번씩 다시 사용해 업데이트되는 노드가 발생하는지 확인한다. 만약 업데이트되는 노드가 있다면 음수 사이클이 있다는 뜻이 되고, 2단계에서 도출한 정답 배열이 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻이 된다. 음수 사이클이 존재하면 이 사이클을 무한하게 돌수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없다.

실제 코딩테스트에서는 벨만-포드 알고리즘을 사용해 최단 거리를 구하는 문제보다 음수 사이클을 판별하는 문제가 더 빈번하게 출제된다. 따라서 마지막에 한 번 더 모든 에지를 사용해 업데이트되는 노드가 존재하는지 확인해야 한다.

업데이트 조건과 방법

D[s] != 무한이며 D[e] > D[s] + w 일 때 D[e] = D[s] + w로 배열의 값을 업데이트한다.

음수 사이클이 없을 때 N - 1번 에지 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단거리를 알려주는 정답 배열이 완성된다. 이렇게 완성 후 마지막으로 이 그래프에 음수 사이클이 존재하는지 확인해야 한다.

코드로 표현

Arrays.fill(distance, Integer.MAX_VALUE); // 최단 거리 배열 초기화하기
for(int i = 0; i < m; i++) {  // 에지 리스트에 데이터 저장하기
	edges[i] = new Edge(start, end, time);
}
// 벨만-포드 알고리즘 수행하기
distacne[1] = 0;
for(int i = 1; i < n; i++) {    // N보다 1개 적은 수만큼 반복하기
	for(int j = 0; j < m; j++) {
    	Edge edge = edges[j];
        // 더 작은 최단 거리가 있을 때 업데이트 하기
        if(distance[edge.start] != Integer.MAX_VALUE
        && distance[edge.end] > distance[edge.start] + edge.time) {
        	distance[edge.end] = distance[edge.start] + edge.time;
         }
    }
}
boolean mCycle = false;
for(int i = 0; i < m; i++) {   // 음수 사이클 확인하기
	Edge edge = edges[i];
    if(distance[edge.start] != Integer.MAX_VALUE
    && distance[edge.end] > distance[edge.start] + edge.time) {
    	mCycle = true;
    }
}
if(!mCycle) {  // 음의 사이클이 없을 때
	for(int i = 2; i <= n; i++) {
    	if(distance[i] == Integer.MAX_VALUE) {
        	System.out.println("-1");
        }
        else {
        	System.out.println(distance[i]);
        }
    }
}
else {   // 음의 사이클이 있을 때 
	System.out.println("-1");
}

class Edge {               // 에지 리스트를 편하게 다루기 위해 클래스로 별도 구현하기
	int start, end, time;  // 시작점, 도착점, 걸리는 시간
    public Edge(int start, int end, int time) {
    	this.start = start;
        this.end = end;
        this.time = time;
    }
}

다익스트라

다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 에지는 모두 양수 이어야 한다. 특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용한다. 

시간 복잡도(노드 수 : V, 에지 수 : E)

O(ElogV)

다익스트라 알고리즘 핵심 이론

1. 인접 리스트로 그래프 구현하기

   다익스트라 알고리즘은 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것 이 좋다. 

2. 최단 거리 배열 초기화하기

   최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화한다. 이때 무한은 적당히 큰 값을 사용하면 된다.

3. 값이 가장 작은 노드 고르기

   최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다. 여기서는 값이 0인 출발 노드에서 시작하면 된다.

4. 최단 거리 배열 업데이트하기

   선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트합니다. 1단계에서 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트하면 된다. 연결 노드 간 최단 거리는 두 값 중 더 작은 값으로 업데이트한다.

5. 과정 3 ~ 4를 반복해 최단 거리 배열 완성하기

   모든 노드가 처리될 때까지 3 ~ 4를 반복한다. 과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 배열을 만들어 처리하고, 모든 노드가 선택될 때까지 반복하면 최단 거리 배열이 완성된다.

최단 거리 업데이트 방법

Min(선택 노드의 최단 거리 배열의 값 + 에지 가중치, 연결 노드의 최단 거리 배열의 값)

다익스트라 알고리즘은 출발 노드와 그외 노드 간의 최단 거리를 구하는 알고리즘이고, 에지는 항상 양수여야 한다는 제약 조건이 있다.

많은 사람들이 다익스트라 알고리즘이 출발 노드와 도착 노드 간의 최단 거리를 구하는 알고리즘이라고 생각하는 경향이 있는데, 실제로 완성된 배열은 출발 노드와 이외의 모든 노드 간의 최단 거리를 표현한다.

코드로 표현

static int[] distance;
static boolean[] visit;
static ArrayList<Edge>[] list;
static PriorityQueue<Edge> q = new PriorityQueue<Edge>();

for(int i = 1; i <= S; i++) {
	list[i] = new ArrayList<Edge>();
}
for(int i = 0; i <= S; i++) {
	distance[i] = Integer.MAX_VALUE;
}
for(int i = 0; i < E; i++) {  // 가중치가 있는 인접 리스트 초기화하기
	list[u].add(new Edge(v, w));
}
q.add(new Edge(k, 0));   // k를 시작점으로 설정하기
distance[k] = 0;
while(!q.isEmpty()) {
	Edge current = q.poll();
    int c_v = current.vertex;
    if(visit[c_v]) {
    	continue;   // 이미 방문한 적이 있는 노드는 다시 큐에 넣지 않음
    }
    visit[c_v] = true;
    for(int i = 0; i < list[c_v].size(); i++) {
    	Edge tmp = list[c_v].get(i);
        int next = tmp.vertex;
        int value = tmp.value;
        if(distance[next] > distance[c_v] + value) { // 최소 거리로 업데이트하기
        	distance[next] = value + distance[c_v];
            q.add(new Edge(next, distacne[next]));
        }
    }
 }
class Edge implements Comparable<Edge> {
	int vertex, value;
    Edge(int vertex, int value) {
    	this.vertex = vertex;
        this.value = value;
    }
    public int compareTo(Edge e) {
    	if(this.value > e.value) {
        	return 1;
        }
        else {
        	return -1;
        }
  	}
}

위의 코드는 알고리즘과 관련된 코드만 표현한 코드입니다. 생략된 부분이 많으니 참고 바랍니다.