데이크스트라 알고리즘[Dijkstra]_(JAVA)

이번 포스팅에서는 양의간선을 갖는 최단거리, 최소비용을 찾을때 사용하는

데이크스트라 알고리즘을 다뤄보도록하겠다.

 

언제 사용되는가?

 

최단거리을 탐색하는 대표적인 알고리즘을 꼽으라면 먼저 BFS를 언급할수 있겠다.

이때 BFS는 간선의 가중치가 모두 동일한 상황에서 사용하기 적합한데 이때 가중치가 모두 다른 상황이라면

BFS 보다는 데이크스트라 알고리즘을 사용하는것이 해당 문제상황을 해결하는것에 더 도움이 될것이다.

 

즉 간선의 가중치가 다른 상황에서 최단거리를 찾고자 할때 데이크스트라 알고리즘을 사용한다.

 

그래서 실사용되는 부분으로는 네트워크 라우팅 프로토콜,

빠른 길찾기(네비게이션), 소셜네트워크 분석(친구찾기) 등 활용도가 높은 알고리즘이다.

 

 

어떻게?

 

데이크스트라 알고리즘은 탐색을 시작할 정점에서 모든 정점의 최단거리를 구하는

알고리즘이고, 각 정점의 최단거리를 계속 갱신해 나가는 식으로 진행이된다.

 

데이크스트라 알고리즘은 다음의 순서에 따라 진행이된다.

 

1. 시작점에서 모든 정점까지의 비용을 일단 무한으로 둔다.
2. 시작점에서 현재 정점까지는 자기자신이므로 비용이 0이다.
3. 이 데이터를 최소힙에 삽입한다.
4. 최소힙에서 데이터를 꺼낸다.
5. 꺼낸 데이터의 비용이 현재 정점까지의 비용보다 큰 경우 다시 데이터를 꺼낸다.
6. 작거나 같은 경우, 꺼낸 데이터의 정점과 연결된 모든 정점을 순회한다.
7. 순회하며 꺼낸 데이터의 정점과 연결된 정점사이의 비용 + 꺼낸 데이터의 비용이 현재 정점의 비용을 비교한다.
8. 현재 정점의 비용이 큰 경우 최소비용을 갱신해주고 최소힙에 이 데이터를 삽입해준다.
9. 최소힙이 비워질 때까지 4 ~ 8 과정을 반복한다.

 

보다 자세한 설명을 위해 그림으로 설명을 진행하겠다.

 

간단한 상황 설정을 하나 해보도록 하겠다.

 

1이란 정점에서 5라는 정점까지 도착할때의 최단거리를 구한다고 가정하고

각 정점 사이의 거리가 다음 그림과 같이 주어진다고 하면,

 

 

 

 

1 >> 3 >> 4 >> 5 로 가는 거리가 10으로 최단거리가 될것이다.

 

 

지금은 아주 단순한 상황이므로 사람이라면 금방 최단거리를 식별할수 있겠지만

당장 정점이 100개만 되더라도 시간이 좀 걸릴것이다.

따라서 이를 컴퓨터에게 시키기위해 데이크스트라 알고리즘을 적용해 살펴보도록 하겠다.

 

먼저 시작점부터 모든 정점까지의 거리를 무한으로 두도록 하겠다.

 

1	2	3	4	5
♾️	♾️	♾️	♾️	♾️

 

 

1번 정점에서 5번정점으로 이동하는 최단거리를 구하기로 했으므로 시작점은 1번 정점이 될것이다.

따라서 1번정점에서 1번정점으로 이동하는 최단거리는 자기자신이므로 0이다.

 

 

1	2	3	4	5
0	♾️	♾️	♾️	♾️

 

 

 

그리고 현재의 정점인 1번 정점에 대한 데이터를 최소힙에 넣도록 하겠다.

 

 

이때 최소힙의 우선순위는 최단거리를 찾아야 하므로 거리를 기준으로 진행한다.

 

이제 힙에서 꺼낸 현재 데이터의 거리와 현재 정점까지의 최단거리가 모두 0으로 같으므로

 

현재 정점인 1번 정점과 연결된 모든 정점을 순회한다.

 

 

 

그리고 연결된 정점들까지의 거리가 현재 표에서 관리하고 있는 최단거리보다 작다면

최단거리를 갱신해주도록 한다.

현재는 모든 정점이 무한이므로 연결된 모든 정점들의 최단거리는 갱신되고 다음 표와 같이 표현할수 있다.

 

 

1	2	3	4	5
0	5	7	♾️	15

 

 

그리고 갱신할때마다 데이터를 최소힙에 삽입해주도록 하겠다.

 

 

이제 다시 최소힙에서 데이터를 꺼내서 연결된 정점을 순회해주도록 하겠다

현재 최소힙에서 꺼낸 데이터는 (정점 : 2, 거리:5) 가 될것이다.

 

 

 

현재 정점인 2번 정점과 연결된 정점은 1번 정점, 4번정점인데

이때 현재 정점까지의 최단거리는 5이고 다시 1번정점으로 돌아간다 가정하면

5 + 5 로 1번 정점과 2번정점의 현재 최단거리인 5보다 크므로 최단거리는 갱신되지 않는다.

 

그리고 4번 정점으로 진행한다면 5 + 6으로 현재의 표에서 관리하는 최단거리인 무한 보다 작으므로

최단거리를 갱신하고 이 데이터를 최소힙에 삽입힌다.

 

갱신된 결과를 다시 표로 작성하자면 다음과 같다.

 

1	2	3	4	5
0	5	7	11	15

 

 

또 최소힙은  다음과 같이 될것이다.

 

 

 

계속해서 다음 데이터인 (정점: 3, 거리: 7)을 힙에서 꺼내 연결된 정점의 순회를 진행한다면,

 

역시 1번 정점으로 돌아간다면 최단거리가 아니므로 갱신하지 않고 4번 정점으로 진행한다면

현재 4번정점까지의 최단거리가 11이고 현재 정점인 3번 정점까지의 최단거리는 7

또 3번 정점에서 4번 정점까지의 거리는 1로 7 + 1 이 현재 최단거리보다 작으므로

최단거리는 갱신되고 힙에 삽입된다.

 

 

1	2	3	4	5
0	5	7	8	15

 

이어서 다음 데이터인 (정점: 4, 거리:8)의 순회를 진행하면 같은 과정을 통해

5번 정점으로 진행되는 최단거리만이 갱신 되어 다음과 같은 결과를 갖는다.

 

 

 

 

1	2	3	4	5
0	5	7	8	10

 

 

 

 

그리고 계속해서 힙에서 데이터를 꺼내 갱신할 데이터가 있는지 순회하다보면

현재 힙에선 더이상 갱신할 데이터가 없으므로 모든 데이터를 꺼내게되고 더이상 탐색을 진행하지 않는다.

 

따라서 정점 1에서 정점 5의 최단거리는 10임을 알수 있게되는것이다.

 

그렇다면 이제 이를 코드로서 구현해보도록 하겠다.

 

 

구현

 

 

먼저 멤버변수로 모든 정점의 정보를 저장할 인접리스트와 최단거리를 저장할 배열을 선언 후

생성자를 통해 주입받도록 하겠다.

 

public class Dijkstra {
	
	private final List<Point>[] edges;
	private final int[] distance;
	
	Dijkstra(final List<Point>[] edges, final int[] distance) {
		this.edges = edges;
		this.distance = distance;
	}
}

 

 

이 객체를 생성할때 찾고자하는 그래프의 정보가 담긴 인접리스트와 모든 최단거리가 무한으로 저장된

배열을 인자로 넘겨주면 될것이다.

 

 

다음으로는 데이크스트라 알고리즘을 실행할 메소드이다.

 

먼저 파라미터로 시작정점을 넘겨 받도록하겠다.

그리고 시작정점까지의 거리는 0으로 주어 자기자신임을 저장한다.

 

	void dijkstra(int start) {
		distance[start] = 0;

	}

 

 

그리고 자바에서 제공하는 자료구조인 우선순위큐를 통해 최소힙을 사용하도록 하겠다.

이때 우선순위는 힙에 저장할 데이터중 거리에 해당하는 데이터를 기준으로 해야하므로 이를 람다를 사용해

재정의 해주도록 하겠다.

 

그리고 바로 최소힙에 현재 데이터를 저장한다.

 

	void dijkstra(int start) {
		distance[start] = 0;
		PriorityQueue<Point> heap = new PriorityQueue<>((o1, o2) -> o1.y - o2.y);
		heap.add(new Point(start, 0));
		
	}

 

 

 

그리고 이제 데이터를 꺼내고 순회하기를 더이상 힙에 데이터가 없을 때까지 반복해야하므로

우선 반복문으로 감싸주도록 하겠다.

 

	void dijkstra(int start) {
		distance[start] = 0;
		PriorityQueue<Point> heap = new PriorityQueue<>((o1, o2) -> o1.y - o2.y);
		heap.add(new Point(start, 0));
		while(!heap.isEmpty()) {
			
		}
	}

 

 

그리고 힙에서 데이터를 하나 꺼내고 해당 데이터와 현재 정점까지의 최단거리를 비교한다

즉 이미 방문했는가를 확인하는 작업인것이다.

 

	void dijkstra(int start) {
		distance[start] = 0;
		PriorityQueue<Point> heap = new PriorityQueue<>((o1, o2) -> o1.y - o2.y);
		heap.add(new Point(start, 0));
		while(!heap.isEmpty()) {
			Point now = heap.remove();
			if(distance[now.x] < now.y) {
				continue;
			}
			
			
		}
	}

 

 

이제 순회를 통해 최단거리를 갱신하고 힙에 데이터 삽입하되 

최단거리인 경우만을 조건으로 선별해준다.

 

	void dijkstra(int start) {
		distance[start] = 0;
		PriorityQueue<Point> heap = new PriorityQueue<>((o1, o2) -> o1.y - o2.y);
		heap.add(new Point(start, 0));
		while(!heap.isEmpty()) {
			Point now = heap.remove();
			if(distance[now.x] < now.y) {
				continue;
			}
			
			for(Point node : edges[now.x]) {
				if(now.y + node.y < distance[node.x]) {
					distance[node.x] = now.y + node.y;
					heap.add(new Point(node.x, distance[node.x]));
				}
			}
		}
	}

 

 

 

이제 앞서 그림으로 표현해왔던 데이터를 이 객체 생성시 넣어주고 

dijkstra 메소드를 호출해 인자로 1을 넣어준다면 1에서 모든 정점에 대한 최단거리를 구할수 있다.

 

		edges[1] = List.of(new Point(2, 5), new Point(3, 7), new Point(5, 15));
		edges[2] = List.of(new Point(1, 5), new Point(4, 6));
		edges[3] = List.of(new Point(1, 7), new Point(4, 1));
		edges[4] = List.of(new Point(2, 6), new Point(3, 1), new Point(5, 2));
		edges[5] = List.of(new Point(1, 15), new Point(4, 2));
		
		Dijkstra dijkstra = new Dijkstra(edges, distance);
		
		dijkstra.dijkstra(1);

 

 

 

 

 

 

아래는 코드의 전문이다.

 

package dijkstra;

import java.awt.Point;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Dijkstra {
	
	private final List<Point>[] edges;
	private final int[] distance;
	
	Dijkstra(final List<Point>[] edges, final int[] distance) {
		this.edges = edges;
		this.distance = distance;
	}
	
	void dijkstra(int start) {
		distance[start] = 0;
		PriorityQueue<Point> heap = new PriorityQueue<>((o1, o2) -> o1.y - o2.y);
		heap.add(new Point(start, 0));
		while(!heap.isEmpty()) {
			Point now = heap.remove();
			if(distance[now.x] < now.y) {
				continue;
			}
			
			for(Point node : edges[now.x]) {
				if(now.y + node.y < distance[node.x]) {
					distance[node.x] = now.y + node.y;
					heap.add(new Point(node.x, distance[node.x]));
				}
			}
		}
	}
	
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		int[] distance = new int[6];
		List<Point>[] edges = new List[6];
		
		Arrays.fill(distance, Integer.MAX_VALUE);
		
		edges[1] = List.of(new Point(2, 5), new Point(3, 7), new Point(5, 15));
		edges[2] = List.of(new Point(1, 5), new Point(4, 6));
		edges[3] = List.of(new Point(1, 7), new Point(4, 1));
		edges[4] = List.of(new Point(2, 6), new Point(3, 1), new Point(5, 2));
		edges[5] = List.of(new Point(1, 15), new Point(4, 2));
		
		Dijkstra dijkstra = new Dijkstra(edges, distance);
		
		dijkstra.dijkstra(1);
		
		for(int i = 1; i < 6; i++) {
			System.out.print(distance[i] + "\t");
		}
	}
}