[알고리즘] 최단 경로 구하기 - 1. 다익스트라

|  다익스트라

- 가중치가 있는 그래프에서, 최단 경로를 구하는 알고리즘

- 핵심 : 그래프의 인접리스트와 DP를 이용

- 기능 : 출발 노드와 모든 노드 간의 최단 거리 탐색

- 특징 : 간선은 모두 양수

- 시간 복잡도 : O(ElogV) * E : 간선수, V : 정점수

 

|  다익스트라 구현

- 배열을 사용하는 것도 좋지만 배열 크기가 너무 클 경우를 대비해 인접 리스트를 사용

- (1),(2) 모두 기본적으로 동일하게 아래를 세팅

(1) 간선 정보 리스트 : 인접 리스트에 Node(연결된 노드, 가중치) 타입으로 저장

(2) 임시 거리 배열 : 출발지부터 노드 X까지의 현재 최소 거리를 업데이트할 배열

ㄴ start 위치는 자기 자신이므로 0으로 세팅한다.

class Node{
    int to;
    int weight;
    
    Node (int to, int weight){
    	this.to = to;
        this.weight = weight;
    }
}

// v : 간선수, data : 각 노드의 간선과 가중치 정보, start : 시작점
public void dijkstra(int v, int[][] data, int start){
    // (1) 간선 정보 업데이트
    ArrayList<ArrayList<Node>> adjList = new ArrayList();
    for (int i = 0; i < v + 1; i++){
    	adjList.add(new ArrayList());
    }
    
    for (int i = 0; i < data.length; i++){
    	adjList.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
    }  
}

// v : 간선수, data : 각 노드의 간선과 가중치 정보, start : 시작점
public void dijkstra(int v, int[][] data, int start){
	// (1) 간선 정보 업데이트
    ArrayList<ArrayList<Node>> adjList = new ArrayList();
    for (int i = 0; i < v + 1; i++){
    	adjList.add(new ArrayList());
    }
    
    for (int i = 0; i < data.length; i++){
    	adjList.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
    }  
    
    // (2) 현재까지 start부터 각 노드들까지 최소거리 dp 배열
    // : 초기값을 무한대(Integer.MAX_VALUE)로 설정한 후, 최소값을 갱신
    int distDP = new int[v + 1];
    for (int i = 1; i < v + 1; i++){
    	distDP = Integer.MAX_VALUE:
    }
    distDP[start] = 0; // start를 0으로 세팅
}

 

1. 방문 배열과 반복문 사용하기

(1) 먼저 방문 배열을 만들고, 첫번째 노드부터 끝 노드까지 현재 지점을 짚는다

// v : 간선수, data : 각 노드의 간선과 가중치 정보, start : 시작점
public void dijkstra(int v, int[][] data, int start){
    // (3) 방문 배열 + 반복문으로 다익스트라 구현
    
    // 방문배열
    boolean[] visited = new boolean[v + 1];
    
    // 반복문
    // start부터 각 노드들까지
    for (int i = 1; i < v + 1; i++){
        int minDistance = Integer.MAX_VALUE; // 최초 거리 : 무한대
        int curIdx = 0; // 최단 거리 노드
        
        // 1부터 V 중에 현재 노드
        for (int j = 1; j < v + 1; j++){
            if (!visited[j] && distDP[j] < minDistance){
            	minDistance = distDP[j];
                curIdx = j;
            }
        }
        
        visited[curIdx] = true;
        
        // 현재 노드에서 
        for (int j = 0; j < adjList.get(curIdx).size(); j++){
            // 연결된 노드들에 대하여
            Node adjNode = adjList.get(curIdx).get(j);
            
            if (distDP[adjNode.to] > distDP[curIdx] + adjNode.weight){
            	distDP[adjNode.to] = distDP[curIdx] + adjNode.weight;
            }
        }
    }
}

- 처음 Start부터 각 노드까지의 최선거리 DP는 모두 무한대(Integer.MAX_VALUE)로 2^32인 2147483647인 상태였다.

1	2	3	4	5
무한대	무한대	무한대	무한대	무한대

- 여기에 앞에서 기본 세팅해줄 때에 Start지점을 0으로 세팅했으므로 현재 상태는 아래와 같다.

1	2	3	4	5
0	무한대	무한대	무한대	무한대

- 위의 for문에서 아래 내용의 distDP[j] > minDistance는 따라서 가장 처음엔 Start값인 1이다.

// 1부터 V의 노드들 중에
for (int j = 1; j < v + 1; j++){
    // 현재 노드 짚기
    if (!visited[j] && distDP[j] < minDistance){
    	minDistance = distDP[j]; // minDistance = distDP[1];
        curIdx = j; // curIdx = 1;
    }
}

- 1 다음부터는 무한대 값인 녀석들을 처음에 curIdx로 짚어주고, 

(2) 현재노드부터 연결된 노드까지의 거리 중 최단 거리를 찾는다.

  (1) 현재까지  X노드까지 거리 : distDP[adjNode.to]

  (2) 새롭게 찾은 X노드까지 거리 : distDP[curIdx] + adjNode.weight 

  이 둘 중에 새롭게 찾은 (2) 가 더 작은 경우 갱신하라는 의미이다.

// 현재 노드에서 
for (int j = 0; j < adjList.get(curIdx).size(); j++){
    // 다시 파생되는 노드들에 대하여
    Node adjNode = adjList.get(curIdx).get(j);

    if (distDP[adjNode.to] > distDP[curIdx] + adjNode.weight){
        distDP[adjNode.to] = distDP[curIdx] + adjNode.weight;
    }
}

	curId	1	2	3	4	5
초기	-	0	∞	∞	∞	∞
1	1	0	2	3	∞	∞
2	2	0	2	3	7	∞
3	3	0	2	3	7	∞
4	4	0	2	3	7	∞
5	5	0	2	3	7	∞

 

2. 우선순위 큐 사용하기

- 우선순위 큐는 원리는 비슷한데, 

- 공간이나 시간 복잡도 면에서 조금 더 개선된 코드이다.

- 하나씩 해보는 것이 필요한 코드..

boolean[] visited;

public void dijkstra(int v, int[][] data, int start){
    // (3) 방문 배열 초기화
    visited = new boolean[v + 1];

    // (4) 우선순위 큐를 통한 다익스트라 구현
    // -- 가중치 기준 오름차순으로 자동 정렬
    PriorityQueue<Node> pq = new PriorityQueue((x, y) -> x.weight - y.weight);
    pq.offer(new Node(start, 0)); // start지점을 0으로 갱신
    
    while (!pq.isEmpty()){
    	Node curNode = pq.poll(); // 현재 지점
        
        if (visited[curNode.to]) { // 방문 했던 곳은 X
            continue;
        }
        visited[curNode.to] = true; 
        
        for (int i = 0; i < adjList.get(curNode.to).size(); i++){ // 최단거리 갱신
            Node adjNode = adjList.get(curNode.to).get(i);
            
            if (!visited[curNode.to] && distDP[adjNode.to] > curNode.weight + adjNode.weight){
            	distDP[adjNode.to] = curNode.weight + adjNode.weight;
                pq.offer(new Node(adjNode.to, distDP[adjNode.to]);
            }
        } 
    }
}

	curNode	pq		1	2	3	4	5
초기	-	(1, 0)		0	∞	∞	∞	∞
1	(1, 0)	(2, 2) (3, 3)		0	2	3	∞	∞
2	(2, 2)	(3, 3) (4, 7)		0	2	3	7	∞
3	(3, 3)	(4, 7)		0	2	3	7	∞
4	(4, 7)			0	2	3	7	∞

 

|  백준 문제 풀이

최단 경로 구하기	https://www.acmicpc.net/problem/1753	😦
최소 비용 구하기	https://www.acmicpc.net/problem/1916	🙃
K번째 최단 경로 찾기

 

 

[ 출처 및 참조 ]

부트캠프 수업 후 정리

Do it! 알고리즘 코딩 테스트