다익스트라 알고리즘

 

먼저 봐야 할 것 

• Graph 탐색 알고리즘

 

 

• 요약

그래프 탐색중에서 최단거리 탐색에 사용되는 알고리즘이며

1. 거리(시간,비용)이 양수로 주어지고

2. 알고리즘을 수행하면 어떤 1개의 node에서 갈 수 있는 모든 node에 대해 최단거리를 구할수있다. 

3. Heap의 자료구조를 사용하여 구현한다. 

 

문제 소개

Graph 탐색

 

---

 

 

사용한 알고리즘

다익스트라 알고리즘

---

 

 

 

 

구상

 

---

 

 

 

Code 소개

# Python code

import heapq
import collections

graph = collections.defaultdict(dict)  # graph 입력받기 위해

#####################################
# graph = {
#    '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(graph, start):

	# distances 처리 
    # distances 는 start (시작node)와 다른 node들 과의 거리를 저장해 놓은 dict이다 
    distances = {node: float('inf') for node in graph}  # 먼저 모든 node 와의 거리를 inf로 설정
    distances[start] = 0  # 자기 자신과 거리는 0 이므로 
    
    # 시작 node를 Q에 삽입한다 
    # Q에는 탐색하는 node들의 ( 항상 start와의 거리 , node ) 값이 저장되어진다.
    Q = []
    heapq.heappush(Q, [distances[start], start])  


    while Q:   
    	# 먼저 Q에서 pop한 node와 distance를 확인한다. 
        # current_distance는 start node와의 거리와 current_destination에는 탐색할 node가 나오게된다
        current_distance, current_destination = heapq.heappop(Q)  
		
        # 그런데 탐색해야하는 node의 거리 current_distance가 
        # distance에 저장되어있는 거리보다 길면 그쪽으로 탐색할 필요가 없다 
        if distances[current_destination] < current_distance:  # 기존에 있는 거리보다 길다면, 볼 필요도 없음
            continue
            
		# 탐색할 node와 연결되어있는 모든 node들의 ( node , 거리 )를 불러온다 
        for new_destination, new_distance in graph[current_destination].items():
            distance = current_distance + new_distance  # 해당 노드를 거쳐 갈 때 거리
            if distance < distances[new_destination]:  # 알고 있는 거리 보다 작으면 갱신
                distances[new_destination] = distance
                heapq.heappush(queue, [distance, new_destination])  # 다음 인접 거리를 계산 하기 위해 큐에 삽입

    return distances

---

 

 

 

마무리

 

다른 Graph 탐색 알고리즘 

 

 

이후에 볼만한 것들

• sssss 

 

---