[알고리즘][Graph] 최단 경로(Shortest Path) #2 최단 경로 문제, Dijkstra 알고리즘

학습목표
1. Bellman-Ford 알고리즘의 문제점
2. Dijkstra 알고리즘에 대해서 학습
3. Dijkstra 알고리즘의 수행과정에 대해서 학습
4. Java 언어 기반 Dijkstra 알고리즘 구현
5. Dijkstra 알고리즘의 시간복잡도에 대해서 학습

 

1. Bellman-Ford 알고리즘의 문제점

Bellman-Ford 알고리즘의 문제점은 특정한 노드의 distance 값이 갱신될때마다 그와 연결된 노드들도 distance 값을 갱신해야 되는 문제점을 가지고 있습니다.

 위의 그림과 같이 노드 V의 distance가 변경될때마다 노드 V와 연결된 노드들도 distance를 갱신해주어야 합니다. 위 문제를 해결하기 위해서는 Relaxtion 연산을 줄일 필요가 있습니다. Relaxtion 연산을 줄이기 위한 방법 중 하나로 다익스트라(Dijkstra) 알고리즘이 있습니다.

 

2. 다익스트라(Dijkstra) 알고리즘은 무엇인가?

다익스트라 알고리즘은 Bellman-Ford 알고리즘처럼 모든 간선에 대해서 노드의 distance 값을 갱신하는 것이 아닌 노드들 중 최소 distance 값을 탐색한 다음 최소값을 가지는 노드의 인접 노드에 대해서만 Relaxtion 연산을 수행하는 알고리즘입니다. 대표적인 특징은 그래프의 음수 가중치 간선이 없다고 가정하고 수행되는 알고리즘입니다.

 

3. 다익스트라 알고리즘 수행과정

1. 시작 노드부터 시작하여 모든 노드까지의 최단 경로를 계산하기 위한 배열 및 집합 초기화
   1. 모든 노드의 distance 값은 ∞로 초기화 (dist 배열), 단, 시작 노드는 0으로 초기화
   2. 최단 경로의 계산이 완료된 집합 S 선언
2. distance 값중 최소인 노드 u를 탐색
3. 최소값인 노드를 집합 S에 합집합
4. u와 인접한 노드들 v에 대해서 Relaxtion 연산 수행
   • Relaxtion(u,v,w) : dist[v] > dist[u] + w인지 검사, dist[u]+w가 더 작다면 최단 경로이므로 dist[v]를 갱신
5. 2~4번 과정을 집합 S가 노드의 개수(V)와 같을때까지 반복

위 수행과정을 그림으로 표현하면 아래와 같습니다.

 

4. Java 언어 기반 다익스트라 알고리즘 구현 O(n²)

	// O(n²)
	public void dijkstra(int start)
	{
		int[] dist = new int[V];
		Set<Integer> s = new HashSet<Integer>();
		
		// step1 초기화
		for(int i=0;i<V;i++)
		{
			dist[i] = Integer.MAX_VALUE;
		}
		dist[start] = 0;
		
		while(s.size()<V)
		{
			int u = findMininumKey(s, dist);
			s.add(u);
			
			for(Edge edge : adj_weight.get(u))
			{
				int v = edge.dest;
				int w = edge.weight;
				
				if(dist[v] > dist[u] + w)
				{
					dist[v] = dist[u] + w;
				}
			}
		}
		
		
		printDistanceFromSource(dist);
	}

public static void main(String[] args)
	{
		int V = 5, E = 10;
		DirectedGraph<String> directedGraph = new DirectedGraph<String>(V,E);
		
		Node<String> s = new Node<String>(0, "s");
		Node<String> t = new Node<String>(1, "t");
		Node<String> x = new Node<String>(2, "x");
		Node<String> y = new Node<String>(3, "y");
		Node<String> z = new Node<String>(4, "z");
		
		directedGraph.addEdge(s, t, 10);
		directedGraph.addEdge(s, y, 5);
		directedGraph.addEdge(t, y, 2);
		directedGraph.addEdge(t, x, 1);
		directedGraph.addEdge(x, z, 4);
		directedGraph.addEdge(y, t, 3);
		directedGraph.addEdge(y, z, 2);
		directedGraph.addEdge(y, x, 9);
		directedGraph.addEdge(z, s, 7);
		directedGraph.addEdge(z, x, 6);
		
		directedGraph.dijkstra(0);
	}

Vertex 		Distance
s		0
t		8
x		9
y		5
z		7

위 다익스트라 알고리즘의 시간복잡도는 O(n²)입니다. 이유는 while문에서 V번 findMiniumKey 메서드에서 최소값을 탐색하기 위해서 V번 순회하기 때문입니다. 위 시간복잡도 문제를 개선하기 위해서 우선순위 큐를 활용하여 최소값 탐색을 개선할 수 있습니다.

 

5. Java 언어 기반 다익스트라 알고리즘 구현, 우선순위 큐 활용 (nlog₂n + mlog₂n)

	// O(nlog₂n + mlog₂n) 
	// 이진힙을 우선순위큐로 사용
	public void dijkstra2(int start)
	{
		int[] dist = new int[V];
		PriorityQueue<Edge> pq = new PriorityQueue<Edge>((v1,v2)->v1.weight - v2.weight);
		Set<Integer> s = new HashSet<Integer>();
		
		// step1 초기화
		for(int i=0;i<V;i++)
		{
			dist[i] = Integer.MAX_VALUE;
		}
		dist[start] = 0;
		
		pq.add(new Edge(start, start, 0));
		
		
		while(pq.size()!=0)
		{
			int u = pq.poll().src;
			s.add(u);
			for(Edge edge : adj_weight.get(u))
			{
				int v = edge.dest;
				int w = edge.weight;
				
				if(!s.contains(v) &&dist[v] > dist[u] + w)
				{
					dist[v] = dist[u] + w;
					pq.add(new Edge(v,v,w));
				}
			}
		}
		
		
		printDistanceFromSource(dist);
	}

위 알고리즘의 시간복잡도는 O(nlog₂n + mlog₂n)입니다.

• while문 : O(n)
• 우선순위를 활용한 최소값 탐색(제거) 후 힙조정 : O(log₂n)
• 노드 u의 인접 노드에 대한 Relaxtion 연산 : degree(u) = O(m)
• pq.add()로 인한 힙 조정 : O(log₂n)

 

References

source code : https://github.com/yonghwankim-dev/inflearn_algorithm/tree/master/graph/graph11_dijkstra_shortestpath
[인프런] 영리한 프로그래밍을 위한 알고리즘 강좌
Geeks For Geeks : https://www.geeksforgeeks.org/dijkstras-algorithm-for-adjacency-list-representation-greedy-algo-8/