Dijkstra Algorithm :: 다익스트라 알고리즘 (최단경로)

---

이 게시물은 개인적으로 알고리즘 공부한 내용과 이곳 저곳 검색하여 얻은 정보, 잡지식을 꾸준히 쌓아가는 글입니다. 출처는 최하단에 남겨두겠습니다. 자료나 궁금한점은 댓글로 질문해주세요.^^ 

---

Dijkstra Algorithm 
다익스트라 알고리즘 = 데이크스트라 알고리즘 

다익스트라 알고리즘 (Dijkstra Algorithm)은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭지점 간의 최단 경로를 찾는 알고리즘입니다. 

출처 : 위키백과

 

이 알고리즘은 컴퓨터 과학자 에츠허르 데이크스트라가 1956년 고안했습니다. 

1930년생이시며, 72세(2002년에 별세하셨다고 하네요.) 

네덜란드 사람이네요. 

 

주요업적 :
다익스트라 알고리즘

프림 알고리즘

차량기지 알고리즘

데드락 방지 알고리즘

은행원 알고리즘

잠자는 이발사 알고리즘

삼색 표시 알고리즘

식사하는 철학자들 문제 ..등등 엄청 많네요....

 

 

아무튼 이런 훌륭하고 천재적인 분이 이 알고리즘을 만들었네요. 

변형이 많은 알고리즘이라고 합니다. 

원래의 알고리즘은 두 꼭지점 간의 가장 짧은 경로를 찾는 알고리즘입니다.

🔽

더 일반적인 변형이 한 꼭지점을 '소스' 꼭지점으로 고정하고 그래프의 다른 모든 꼭지점까지의 최단 경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것입니다.

최초 다익스트라 알고리즘은 우선순위 큐를 사용하지 않았습니다.

그래서 최초 시간 복잡도는 

(|V|는 꼭지점의 갯수입니다.)

최소 우선순위 큐에 기반한 알고리즘은 피보나치의 힙 으로 수행되며 시간 복잡도는 

(|E| 는 변의 갯수입니다.) 으로 바뀝니다. 

---

이 알고리즘의 배경은 생각보다 단순한 생각에서 시작되었습니다.

'로테르담에서 흐로닝언까지, 일반적으로 한 도시에서 다른 도시로 가는 가장 짧은 길이는 무엇일까요?'

"이것은 제가 이십 분 동안 생각해낸 최단 거리를 찾는 알고리즘입니다. 어느 날 아침에 저는 제 약혼녀와 암스테르담에서 쇼핑을 하고 있었고, 지쳤었기 때문에 카페 테라스에 앉아서 커피를 마시며 그 문제에 대해서 생각하다가 최단 거리를 찾는 알고리즘을 고안했습니다. 제가 말했듯, 이것은 이십 분 짜리 발명품입니다. 사실, 이 알고리즘은 삼 년 뒤인 1959년에 발표했습니다. 그 간행물을 여전히 읽을 수 있습니다. 사실은 꽤 괜찮습니다. 이것이 괜찮은 이유 중 하나는 제가 이 알고리즘을 고안할 때 연필과 종이 없이 고안했다는 것입니다. 제가 나중에 알게 된 바로는 연필과 종이 없이 고안하는 것의 좋은 점은 고안 할 때 피할 수 있는 복잡성을 피하도록 거의 강요되기 때문입니다. 갑자기 그 알고리즘이 나타남이 저를 놀랍게 했으며 제 명성의 초석이 되었습니다."
-- 에츠허르 데이크스트라 , Philip L과의 인터뷰에서 

짧은 시간에 단지 생각만으로 컨셉을 잡고 생각해냈다는 것 자체가 놀라웠습니다. 

하지만, 어찌보면 모든 사람들이 이러한 생각을 하고는 산다고 생각합니다. 

 

역시 개발자들은 이러한 일상의 문제를 해결하기 위해 기술적으로 어떻게 해결할지 코드화 시키는, 이론화 시키는 것이 습관적으로 해내야 한다고 생각이 드는 부분이었습니다. 

---

다익스트라의 개념은 출발점에서 이동 가능한 노드(꼭지점)을 찾고, 그 거리를 다 기록합니다. 그리고 그 거리들 중 가장 짧은 것을 선택하고 이동합니다. 이런식의 작업을 도착점까지 갈때까지 반복하며, 도착점까지의 거리 경로를 쭈욱 리턴해주면, 가장 짧은 경로를 보여주게 되는 컨셉입니다. 

이제 코드로 알아보겠습니다. 

소스코드로 알아보는 부분은 파이썬으로 주로 알아보고, 제가 시간이되거나 더 연구하고 싶으면 다른 언어로도 구현해보는 방향으로 하겠습니다. 

 

코드에 들어가기 앞서 다익스트라의 필수 개념은 우선순위 큐입니다.
우선순위 큐는 Python heapq 라이브러리를 활용하여 구현합니다.

우선순위 큐

# 우선순위 큐의 사용방법이다.
import heapq
queue = []
  heapq.heappush(queue, [2,'A'])
  heapq.heappush(queue, [5,'B'])
  heapq.heappush(queue, [1,'C'])
  heapq.heappush(queue, [7,'D'])
  print(queue)

OUTPUT :

[[1, 'C'], [5, 'B'], [2, 'A'], [7, 'D']]

heapq라이브러리르 활용하면, 노드(예를들어, [2, 'A'] 에서의 2가 노드입니다.)가 가장 작은 1이 맨 앞으로 해서 출력이 됩니다. 그 이후는 딱히 순서가 없습니다. 

여기서 잘 봐야할 부분은

heapq.heappush(공간, 들어갈 값)

heappush 메서드를 활용하여 우리가 원하는 노드들을 다 넣어줍니다. 

 

그리고 여기서 만약 노드의 오름차순으로 정렬하고자 한다면, 

for index in range(len(queue)):
	print(heapq.heappop(queue))

이 반복문을 추가하면 됩니다. 이런 경우 출력결과는...

[1, 'C']
[2, 'A']
[5, 'B']
[7, 'D']

이렇게 됩니다. 노드의 숫자순으로 나열이 된것이 보이시나요. 

그리고 여기서 힙에 들어간 값을 뽑아내는 메서드

heapq.heappop(공간)

이 heappop을 통해 출력을 하게 됩니다. 반복문 range(len(queue))를 통해서 큐의 범위를 선정해주면서 index를 넣어

출력해주면 오름차순 순서대로 출력이 됩니다.

---

다익스트라 알고리즘

1 단계 : 데이터 수집

이 그림이 지도라고 생각하면서 보면 더 이해가 잘 됩니다. 이 그림을 코드로 표현해보면, 

#동네 거리 저장 배열
mycountry = {
    'A': {'B':8, 'C':1,'D':2},
    'B': {},
    'C': {'B':5, 'D':2},
    'D': {'E':3,'F':5},
    'E': {'F':1},
    'F': {'A':5}
}

이런 식으로 표현이 됩니다.  이렇게 동네의 길 종류를 다 적어줬다고 생각하면됩니다. 

예를들어, 

출발점 = 집 = A 

B, C, D = 편의점, 세탁소, 부동산 이라고 생각하면됩니다. 

이런 경우 집에서 B 편의점으로 가는 길 거리는 8인 것입니다. C 세탁소 거리는 1, D 부동산 거리는 2인 것입니다. 

 

이러한 방법등으로 현실 속의 데이터를 코드로 저장하는 것입니다. 

그래서 전 이 과정이 데이터의 수집 단계라고 보았습니다. 

---

2 단계 : 초기화

다음 작업은 함수를 구현하는 부분 중 일부입니다. 

먼저, 만들어 놓은 동네의 장소들 별 거리의 배열을 heap queue에 넣어줄 수 있게 비어있는 거리 배열을 만들어줍니다.

import heapq

def dijkstra(country, start): 
    # 최초 구성은inf로 비어있는 상태로 만듭니다. 
    country = {node:float('inf') for node in country}
    # 출발점은 거리가 0입니다.
    country[start] =0 
    # 우선순위 큐를 선언해줍니다.
    heap = []
    # 우선순위 큐에 출발점 값을 넣어줍니다.
    heapq.heappush(heap, [country[start],start])
    
#초기화 완료

출발점의 거리는 0, 나머지는 무한대. 

'inf'라고 무한대라고 표현하는 값을 일단 넣어줍니다. = 거리가 무한대라는 것이 아니라 아직 거리를 모른다고 보면 됩니다. 

A	B	C	D	E	F
0	inf	inf	inf	inf	inf

distance 라는 거리 배열을 선언해주고, 사이즈를 우리가 입력할 데이터의 값이라고 생각하고 기본값 inf를 넣어줍니다. 

country= {node : float('inf') for node in country)

queue 라는 우선순위 큐 배열을 선언해주고, 그 안에는 출발점인 A 만 넣어줍니다. A 의 거리는 0으로 선언했었습니다.

heap= []
heapq.heappush(heap, [country[start],start]) 

이렇게 하면 위의 표처럼 초기화 작업이 완료 됩니다. 

---

3 단계 : 출발점에서 각 지점과의 거리 입력

A	B	C	D	E	F
0	8	1	2	inf	inf

표로 보면 최초 출발점에서 갈 수 있는 지점은 B, C, D입니다. 
그러므로, 그 최초의 거리를 입력해주고, 못가는 부분은 inf로 남게 하는 작업입니다. 

while heap :
	current_distance, now_position = heapq.heappop(heap)

	if country[now_position] < current_distance : 
		continue

	for arrival, weight in road[now_position].items() :
		distance = current_distance + weight

		if distance < country[arrival] :
			country[arrival] = distance
			heapq.heappush(heap, [distance, arrival])

return country

---

current_distance, now_position = heapq.heappop(heap)
...
for arrival, weight in road[now_position].items() :
distance = current_distance + weight

🌞  'A': {'B': 8, 'C': 1,'D': 2}  A의 값들은 B-8 , C-1 , D-2 이라는 내용들이 있습니다. 

이 것들을 작업해주는 반복문입니다. 

now_position 은 A라고 보시면됩니다. 

그리고 그것들의 items() 메서드를 통해서 안에 있는 값들을 꺼내옵니다. 그리고 안에 있는 것들도 노드와 값을 가지고 있으므로 그것들의 명칭을 정해줍니다. arrival 과 weight 로 말입니다. 

그리고 distance라는 거리 객체를 선언해주면서 current_distance = 0 과 weight 안에 있던 각 노드들의 거리를 더해서 거리 객체를 한번씩 완성해줍니다. 

---

4단계 : 거리를 비교하여 최단 거리를 업데이트 시켜준다.

if distacne < country[arrival] : 
      country[arrival] = distance
      heapq.heappush( queue, [distance, arrival] ) 

이 가정문을 통해서 counrty[arrival] 도착지점까지의 거리가 있다면, 그값과 Distance 객체의 값을 일단 비교해주고 

distance가 작다면, country[arrival] 을 distance로 바꿔주고, 

perfect 배열에도 이 Distance와 Arrival을 업데이트 시켜줍니다.

---

이렇게 최종적으로 반복을 다하면 각 노드에 가는 길의 최소 거리를 구해서 각 노드의 거리에 입력이 되는 것입니다. 

 

최종 OUTPUT>>

{'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}

아 if country[now_position] < current_distance :  continue 라는 코드를 추가해서 불필요한 계산을 방지해주면 더 빨라지는 효과가 있습니다. 

 

전체 소스코드

mycountry = {
    'A': {'B': 8, 'C': 1,'D': 2},
    'B': {},
    'C': {'B': 5, 'D':2},
    'D': {'E': 3, 'F':5},
    'E': {'F': 1},
    'F': {'A': 5}
}

import heapq

def dijkstra(road, start): 
    
    country = {node:float('inf') for node in road}
    country[start] =0 
    heap = []
    heapq.heappush(heap, [country[start],start])
    
    while heap :
        current_distance, now_position = heapq.heappop(heap)

        if country[now_position] < current_distance : 
            continue
        
        for arrival, weight in road[now_position].items() :
            distance = current_distance + weight
            
            if distance < country[arrival] :
                country[arrival] = distance
                heapq.heappush(heap, [distance, arrival])
        
    return country

dijkstra(mycountry, 'A')

 

이상입니다. 

 

다익스트라 알고리즘은 정보처리기사에서도 나오는 개념인데,  세부적이게 어떻게 구현하는지 알게되어 좋은 공부가 되었습니다. 

 

---

2020.07.27 

코드를 좀더 잘 이해되도록 바꿨습니다. 큰 차이는 없고 변수명과 주석을 추가했습니다. 

import heapq
def dijkstra(country, startPoint):
        # 최적화된 도로망이라는 country_opt_road 배열을 선언과 동시에 inf로 비어있는 상태로 
        # 선언해준다. input 되는 country에 있는 노드를 찾아서 포인트별로 저장하고
        # 그 안의 값들은 일단 inf로 초기화 하는 작업의 코드
        country_opt_road = {node: float('inf') for node in country}
        # 최초 출발점은 input되는 startPoint로 설정하여 0으로 설정한다. 
        country_opt_road[startPoint] = 0 
        # 잠시 데이터를 쌓아둘 공간을 설정한다. 이 공간은 
        heap = []
        # heap공간에 Startpoint지점의 정보와 거리 0을 넣어준다. 
        heapq.heappush(heap, [country_opt_road[startPoint], startPoint])
        
        # heap 
        while heap :
            distance , position = heapq.heappop(heap)
            if country_opt_road[position] < distance :
                continue 
            # input되는 country 데이터 안의 position이 가지는 초기값의 안의 정보를
            # 가져온다. 그리고 안의 정보를 arrival , distance2로 나눠서 구분한다. 
            # B, 8이 나오고 기존의 inf를 바꿔주는 방식을 진행한다. 
            # 다음 arrival, distance2도 같은 작업을 해주고 
            # 끝이나면, 다음 노드로 넘어가서 그 노드의 items()를 가져와서 
            # 같은 작업을 반복
            for arrival, distance2 in country[position].items() :
                opt_distance = distance + distance2 
                # 이부분을 통해 이전의 거리 계산 된 것과 비교하여 지금의 거리 값이
                # 더 효율적이면 바꿔주는 코드이다. 
                if opt_distance < country_opt_road[arrival] :
                    print('최적화 작업 발생', arrival,'포인트에서 발생')
                    country_opt_road[arrival] = opt_distance 
                    heapq.heappush(heap, [opt_distance, arrival])
                    print(arrival ,country_opt_road)
        return country_opt_road

 

😏 최단거리 경로 출력 방법 

(저도 공부하는 입장이라 이 사이트를 참조하시면 더 좋을 거 같네요!)

제 풀이는 저도 이해하고자 주석을 붙인게 전부입니다. ㅎㅎ 참고하세요!!

mycountry = {'A': {'B': 8, 'C': 1, 'D': 2}, 'B': {}, 'C': {
    'B': 5, 'D': 2}, 'D': {'E': 3, 'F': 5}, 'E': {'F': 1}, 'F': {'A': 5}}

def dijkstra_road(matrix, start, end):
	# 초기 노드들을 넣어줄 공간을 구성합니다. 
    search_load = {node: [float('inf'), start] for node in matrix}
    search_load[start] = [0, start]
    print('초기값:', search_load)

    # 최적화 길의 노드들을 저장하기 위한 리스트 선언합니다.
    temp = []
    heapq.heappush(temp, [search_load[start][0], start])
    print('초기큐:', temp)

    while temp:

        현재거리, 현재노드 = heapq.heappop(temp)
        print('노드:', 현재노드, '거리:', 현재거리)

        if search_load[현재노드][0] < 현재거리:
            continue

        for 노드, 거리 in matrix[현재노드].items():

            최신거리 = 현재거리 + 거리
            print('최신거리:', 최신거리)

            if 최신거리 < search_load[노드][0]:
                print('더 짧은 거리 발견')
                search_load[노드] = [최신거리, 현재노드]
                heapq.heappush(temp, [최신거리, 노드])

	# sear_load는 출발점으로부터 해당 노드까지의 거리를 나타냅니다.
    # 경로를 알기 위해서는 아래와 같이 역 추적으로 노드를 구해내면 됩니다.
    opt_path = []
    opt_path.append(end)
    path = end
    while search_load[path][1] != start:
        opt_path.append(search_load[path][1])
        path = search_load[path][1]

    opt_path.append(start)

    print('목적지에서 시작점으로 거꾸로 출력이 됩니다.',opt_path)
    
    # 이부분을 join으로 역으로 출력해주면 됩니다.
    return '->'.join(opt_path[::-1])


print(dijkstra_road(mycountry, 'A', 'F'))   # A->D->E->F

 

 

---

도움이 되셨다면 공감♥ 버튼 부탁드립니다.

---