[Ch.09 - Greedy] 05. 다익스트라 알고리즘

728x90

다익스트라 알고리즘
아래의 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소 거리비용을 출력하는 프로
그램을 작성하세요. (경로가 없으면 Impossible를 출력한다)

입력설명
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연
결정보와 거리비용이 주어진다.

출력설명
1번 정점에서 각 정점으로 가는 최소비용을 2번 정점부터 차례대로 출력하세요.

입력예제 1

6 9
1 2 12 // 1번 정점에서 2번정점으로 가는데 12의 비용이 든다.
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5

출력예제 1

2 : 11
3 : 4
4 : 9
5 : 14
6 : impossible

다익스트라 알고리즘

: 어느 한 지점에서 다른 지점까지의 최단 경로를 찾는 알고리즘

-> 음의 가중치가 없고, 항상 0이거나 양의 가중치만 존재할때 사용 가능한다.

따라서, 가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용할 수 있다.

문제 풀이 순서

1. 아직 확인되지 않은 거리는 전부 초기값을 무한으로 잡는다.
2. 루프를 돌려 이웃 노드를 방문하고 거리를 계산한다.
3. 첫 루프 이후의 그래프의 상태가 업데이트되는 방식
4. 더 빠른 경로를 발견한 경우, 이전의 경로 값을 대체한다.

(P[A][B]는 A와 B 사이의 거리라고 가정한다)

출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. (정말 무한이 아닌, 무한으로 간주될 수 있는 값을 의미한다.) 보통은 최단거리 저장 배열의 이론상 최대값에 맞게 INF를 정한다. 실무에서는 보통 d의 원소 타입에 대한 최대값으로 설정하는 편.[6][7]
현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다.
A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B][8]와 d[B][9]의 값을 비교한다. INF와 비교할 경우 무조건 전자가 작다.
만약 d[A] + P[A][B]의 값이 더 작다면, 즉 더 짧은 경로라면, d[B]의 값을 이 값으로 갱신시킨다.
A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.
A의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 A는 사용하지 않는다.
"미방문" 상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.
도착 노드가 "방문 완료" 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.

(+ 다익스트라의 은행원 알고리즘

: 병렬 수행 프로세스 간에 데드 록(dead lock)을 막기 위해 네덜란드의 과학자 다익스트라(Dijkstra, E. W.)가 제의한 알고리즘. 프로세스가 요구한 자원의 수가 현재 사용 가능한 자원의 수보다 작을 때 프로세스가 요구한 수만큼 더 자원을 할당하는 방식)

문제 구현 순서

정점의 수만큼 거리 배열의 크기를 선언 한다.
거리 배열을 모두 최댓값으로 초기화한다.
즉, 거리 배열 dis[i]은 최소비용 1번 정점에서 부터 i번 정점까지의 최소 비용을 저장하는 배열이다.
출발정점은 0으로 초기화한다.
M이 아닌 값중에 최솟값을 찾는다.
1. 출발 정점인 dis[0]이 최솟값인 0이므로, 0에서 시작
2. 1번 정점에서는 2번이나, 3번으로 갈 수 있으므로,
  1. dis[i]값보다 더 작으면 변경
  2. dis[2]는 0+12 저장, dis[3]은 0+4 저장
  3. 해당 위치에서 최솟값을 찾는데, 이미 한번 돈, 1전 정점은 제외한다.
    1. dis[3]이 4이므로, 최솟값으로 선택된다.
    2. 3번 정점에서는 4번으로 갈 수 있으므로,
      1. dis[i]값보다 더 작으면 변경
      2. dis[4]는 4+5 저장
      3. 해당위치에서 최솟값을 찾는데, 이미 한번 돈, 1번 정점과 3번 정점은 제외한다.
        
        dis[4]가 9이므로, 최솟값으로 선택된다.
        
        4번 정점에서는 2번과 6번으로 갈 수 있으므로,
        
        dis[i]값보다 더 작으면 변경
        
        dis[2]는 9+2인데 기존의 dis[2]가 12이므로 11저장, dis[6]은 9+5 14 저장
        
        해당위치에서 최솟값을 찾는데, 이미 한번 돈, 1번 정점, 3번 정점, 4번 정점은 제외한다.
        
        dis[i]값보다 더 작으면 변경
        
        dis[2]가 11이므로 최솟값으로 선택된다.
        
        2번 정점에서는 1번, 5번으로 갈 수있으므로,
        
        dis[i]값보다 더 작으면 변경
        
        dis[1]은 11+2인데 기존의 dis[1]이 0이므로, 변경하지 않고,
        dis[5]는 11+5로 dis[5]은 14이므로 변경하지 않는다.
        
        해당 위치에서 최솟값을 찾는데, 이미 한번 돈 1번, 2번, 3번, 4번은 제외한다.
        
        5번정점에서 갈 수 있는 방향이 존재하지 않으므로 종료

최솟값을 찾기 위해서는, 시간 복잡도 O(n)이므로, 최소한 정점의 개수만큼 해야한다. -> n * n

-> 효율성을 위해 시간복잡도 logn으로 가능한 방법을 이용 -> n * log n

PriorityQueue를 이용해 시간 복잡도 logn으로 줄인다.

-> 우선순위큐는 이진트리로 구성되어 있으므로, logn의 시간복잡도를 가진다.

우선순위큐를 이용하면, 1번 정점에서 2번 정점과 3번 정점으로 이동하는 경로의 최솟값을 찾는 행위에서 logn의 시간복잡도를 이용해 찾을 수 있다.

-> dis[2]= 14, dis[3] =4 -> PriorityQueue -> dis[3]인 4를 반환

알고리즘 구현

그래프에 가중치까지 존재하므로, Edge라는 객체를 이용해 인접리스트 선언
Edge 클래스는 정점과 비용을 가진 객체 -> 정점 번호와 가중치 값을 저장
ArrayList<ArrayList<Edge>> graph -> 엣지라는 객체를 저장할 수 있는 리스트를 저장하는 리스트 선언
그래프 선언 후, for(0~n) 정점 개수만큼 반복해 그래프에 엣지라는 객체를 저장할 수 있는 리스트를 삽입
간선 개수만큼, 반복해 그래프의 정점에 간선 삽입
-> a, b, c : a라는 정점에서 b라는 정점으로 c라는 가중치를 이용해 이동
int a=kb.nextInt(); int b=kb.nextInt(); int c=kb.nextInt();
graph.get(a).add(new Edge(b,c));
정점이 1번 정점부터 존재하고, 1번이 출발점이므로 다익스트라 시작
solution(1);
1. 우선순위큐를 선언
  compareTo (Edge ob) -> return this.cost-ob.cost;
  : 가장 작은 비용을 우선순위로 하는 큐
2. 우선순위 큐에 초기값 입력
  pQ.offer(new Edge(v, 0)); [정점 v, 비용 0]
3. 우선순위 큐의 시작 정점에 [거리 0 입력]
  dis[v]=0;
4. 큐가 빌때까지 최단거리 배열 dis[i] 채우기
5. 현재 정점을 큐에서 꺼내서, 해당 정점과 비용을 저장
6. 만약, 현재 정점의 최단경로보다 현재 정점의 비용이 크면, continue;
7. 최단 경로가 될 수 있는 가능성이 존재한다면,
8. 그래프에서 현재정점에서 갈 수 있는 정점을 돌면서 최단 경로 찾기
  for(Edge ob:graph.get(now)) : 해당 정점에서 이어진 모든 간선정보
  1. 현재 비용에 간선 비용 추가했을 때, 현재 정점의 비용보다 작으면
    if(dis[ob.vex]>nowCost+ob.cost)
  2. 현재 비용에 간선 연결한 비용으로 변경
    dis[ob.vex]=nowCost+ob.cost;
  3. 해당 정점에서의 경로가 최단 경로가 될 가능성이 존재하므로, 변경한 이후에 큐에 추가
    pQ.offer(new Edge(ob.vex, nowCost+ob.cost));
    1. 1번정점부터 시작했으므로, 해당 정점에서 이동한 다음 정점부터 최단 경로 찾기 반복
      for(int i=2;i<=n;i++) {
    2. 경로가 무제한이 아니면, 최단 경로 출력
      if(dis[i]!=Integer.MAX_VALUE) {
    3. 무제한이면, 도달 불가능 출력
      System.out.println("Impossible");

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;


public class Main {
	static int n,m;
	static ArrayList<ArrayList<Edge>> list;
	static int[] dis;


	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		m=kb.nextInt();

		list = new ArrayList<ArrayList<Edge>>();
		dis = new int[n+1];
		//정점의 개수를 배열의 크기하는 최단 경로 배열 선언 
		Arrays.fill(dis, Integer.MAX_VALUE);
		
		for(int i=0;i<=n;i++) {
			list.add(new ArrayList<Edge>());
		}
		//ArrayList<Edge>를 담는 ArrayList에 정점의 개수만큼 ArrayList<Edge>를 삽입
		
		for(int i=0;i<m;i++) {
			int a=kb.nextInt();
			int b=kb.nextInt();
			int c=kb.nextInt();
	
			list.get(a).add(new Edge(b,c));
		}
		//간선의 개수만큼 도는데, 해당 정점에서의 간선을 추가해야하므로,
		//list에서 a라는 정점을 get해서 필요한 간선을 Edge객체에 추가하는 방식
		
		//list : ArrayLis<Edge>를 담는 ArrayList
		//list.get(정점) : 정점에서의 ArrayList<Edge>에 간선 Edge를 추가
		solution(1);
		for(int i=2; i<=n;i++) {
			if(dis[i]!=Integer.MAX_VALUE) {
				System.out.println(i+": "+dis[i]);
			}
			else
				System.out.println("Impossible");
		}
	}
	static void solution(int v) {
		PriorityQueue<Edge> q= new PriorityQueue<>();
		//초기값 설정
		q.offer(new Edge(v,0));
		//정점 1, 비용 0을 삽입
		dis[v]=0;
		//최단 경로 배열에 출발정점에 0지정
		
		//큐가 빌 때까지 최단 경로 배열을 채운다.
		while(!q.isEmpty()) {
			Edge tmp = q.poll();
			int now=tmp.vex;
			int nowCost=tmp.cost;
			
			if(dis[now]<nowCost) continue;
			//현재 정점의 최단 경로보다 현재 정점의 비용이 크면 continue;
			
			for(Edge ob : list.get(now)) {
				//현재정점에서의 이동가능한 모든 간선을 확인
				if(dis[ob.vex]>nowCost+ob.cost) {
					dis[ob.vex]=nowCost+ob.cost;
					q.offer(new Edge(ob.vex, nowCost+ob.cost));
				}
			}
		}
	}

}

+) 세련된 풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Edge implements Comparable<Edge>{
	public int vex, cost;
	Edge(int vex, int cost) {
		this.vex=vex;
		this.cost=cost;
	}
	@Override
	public int compareTo(Edge ob) {
		return this.cost-ob.cost;
		//오름차순
	}
}

class Main {
	static int n, m;
	static ArrayList<ArrayList<Edge>> graph;
	static int[] dis;
	public void solution(int v) {
		PriorityQueue<Edge> pQ=new PriorityQueue<>();
		pQ.offer(new Edge(v,0));
		dis[v]=0;
		while(!pQ.isEmpty()) {
			//비어있지 않으면 계속 반복
			
			Edge tmp=pQ.poll();
			int now=tmp.vex;
			int nowCost=tmp.cost;
			//현재값 저장
			
			if(nowCost>dis[now])
				continue;
			//현재값과 거리배열과 비교해 현재값이 크면 비교하지 않고 넘어간다.
			
			for(Edge ob:graph.get(now)) {
				if(dis[ob.vex]>nowCost+ob.cost) {
					//현재 비용에 간선 비용 추가했을 때, 현재 정점의 비용보다 작으면 
					
					dis[ob.vex]=nowCost+ob.cost;
					//현재 비용에 간선 연결한 비용으로 변경
					pQ.offer(new Edge(ob.vex, nowCost+ob.cost));
					//큐에 추가 -> 간선의 정점, 비용 
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb= new Scanner(System.in);
		n = kb.nextInt();
		m=kb.nextInt();
		
		graph=new ArrayList<ArrayList<Edge>>();
		Arrays.fill(dis, Integer.MAX_VALUE);
		//다익스트라 알고리즘은 항상 모든 거리에 최댓값을 넣는다.

		for(int i=0;i<m;i++) {
			int a=kb.nextInt();
			int b=kb.nextInt();
			int c=kb.nextInt();
			graph.get(a).add(new Edge(b,c));
			//A기준 B로 가는 간선 생성
		}
		T.solution(1);
		for(int i=2;i<=n;i++) {
			if(dis[i]!=Integer.MAX_VALUE) {
				//거리 배열이 무제한이 아니면 출력
				System.out.println(i+" "+dis[i]);
			}else {
				//무제한이면 Impossible 출력
				System.out.println("Impossible");
			}
		}
		
	}

}

#다익스트라 알고리즘

while(!pQ.isEmpty()) {
    //비어있지 않으면 계속 반복

    Edge tmp=pQ.poll();
    int now=tmp.vex;
    int nowCost=tmp.cost;
    //현재값 저장

    if(nowCost>dis[now])
        continue;
    //현재값과 거리배열과 비교해 현재값이 크면 비교하지 않고 넘어간다.

    for(Edge ob:graph.get(now)) {
        if(dis[ob.vex]>nowCost+ob.cost) {
            //현재 비용에 간선 비용 추가했을 때, 현재 정점의 비용보다 작으면 

            dis[ob.vex]=nowCost+ob.cost;
            //현재 비용에 간선 연결한 비용으로 변경
            pQ.offer(new Edge(ob.vex, nowCost+ob.cost));
            //큐에 추가 -> 간선의 정점, 비용 
        }
    }
}

728x90

저작자표시 비영리

'Java > Java 알고리즘 인프런' 카테고리의 다른 글

[Ch.09 - Greedy] 07. 원더랜드 (+ 최소스패닝트리 : 크루스칼, Union & Find) (1)	2022.08.20
[Ch.09 - Greedy] 06. 친구인가 (+ Disjoint-Set : Union & Find) (0)	2022.08.20
[Ch.10 - DP] 06. 최대점수 구하기 [+냅색 알고리즘] (0)	2022.08.03
[Ch.10 - DP] 05. 동전교환 [+냅색 알고리즘] (0)	2022.08.03
[Ch.10 - DP] 04. 가장 높은 탑 쌓기[+LIS] (0)	2022.08.01

Just do it, and then some

[Ch.09 - Greedy] 05. 다익스트라 알고리즘

'Java > Java 알고리즘 인프런' 카테고리의 다른 글

티스토리툴바

[Ch.09 - Greedy] 05. 다익스트라 알고리즘

'Java > Java 알고리즘 인프런' 카테고리의 다른 글

'Java/Java 알고리즘 인프런' Related Articles

티스토리툴바