1. 개요

• 일반적으로는 BFS를 사용하면 vertice간 최단거리를 구할 수 있다. 다만, 이 경우는 edge에 weight가 없을 경우에 한정한다.

• Weight가 존재하는 경우, 다른 방식이 필요하다.

2. 다익스트라 알고리즘

• 그래프 내의 한 vertice에서 다른 vertice까지의 최단거리를 구하는 일에 사용하는 알고리즘으로, 다음의 조건이 필요하다.

  	1. 그래프는 weighted여야 한다.
  	2. Weight는 음수가 아니어야 한다.
  	3. 그래프 내에 존재하는, 닿을 수 있는 모든 vertice를 대상으로 구한다.

• 알고리즘의 구축에는 Priority Queue, VisitedSet, Map이 필요하다. PQ에서는 가장 작은 값이 우선적으로 나와야 한다.

Dijkstra(G, s)
	VisitedSet, VS
    DistanceMap, DM
    PriorityQueue, PQ
    for v in G
    	add v in DM, initialize distance as infinity
    PQ.enqueue(s,0)
    while PQ is not empty && VS not full
    	(u, d) = PQ.dequeue
        if u is not in VS
        	u in VS
            update DM's u with new distance
            for (w, d2) adjacent to u && not in VS
            	PQ.enqueue(w, d+d2)

• DM에 모든 vertice는 거리가 무한인 상태로 들어가 있다.

• 최초의 PQ에서 starting vertice가 나오면, 거리 0인 상태로 DM에 업데이트를 한 후, 이와 인접한 모든 vertice를 PQ에 넣는다.

• 이후 PQ에서는 시작지점에서 가장 가까운 vertice가 나오고, VS에 더함과 동시에 DM의 거리값을 업데이트한다. 이상태에서 해당 vertice의 이웃들이 PQ에 더해지는데, 이때 시작지점에서의 기존 거리를 더한 거리가 PQ에 들어간다.

• 그 다음으로 거리가 가까운 vertice가 계속해서 PQ에서 나온다. 끝날때까지 반복한다.

• 기본적으로 시간복잡도는 O(E log E)이다.

출처: https://learning.edx.org/course/course-v1:GTx+CS1332xIV+2T2020/home

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.