[Algorithm] - 다익스트라

다익스트라

---

방향, 무방향 그래프에서 하나의 시작점으로 부터 다른 Node까지의 최단 거리를 구하는 알고리즘

• Edge에 음수인 가중치가 있다면 절대 사용 불가!
• 유사 알고리즘으로 A* 알고리즘이 존재하지만, 길찾기와 같이 Node가 엄청 많을 때 유사값을 찾는 용도이다.
• 거리가 확정되지 않은 Edge 중에서 가장 가까운 Edge를 선택한다는 그리디 알고리즘으로 부터 착안한다.
• O(V^2+E) => 갱신 가능
• 아래와 같은 그래프에서 1부터 시작한다면, 각 Node별로 최단 거리 값이 결과가 나타난다.

Graph

• 1에서는 갈 수 있는 Node가 2,3,4 총 3가지다.
• 이중에서 가장 작은 Edge는 Node 3과 연결된 2로 갱신 시키고 Node에 대해 확정을 시켜준다.
• 연결된 가장 작은 Edge는 Node 2와 연결된 3으로 갱신시키고 Node에 대해 확정 시켜준다.
• 위와 같이 계속하여 반복하여 준다면, O(V^2+E) 을 통하여 구현 할 수 있다.

# 다익스트라
import sys
graphs = [[1,2,3],[1,3,2],[1,4,5],[2,3,2],[2,5,8],[3,4,2],[4,5,6],[5,6,1]]

#init
start = 1
n = 6
table = [sys.maxsize]*(n+1)
visited = [0]*(n+1)

table[start]=0
visited[start]=1
visited[0]=1
node = [[] for _ in range(n+1)]

#graph
for st,ed,value in graphs :
    node[st].append((ed,value))

for i in range(n-1):
    # 최단 거리 Table 갱신
    for end,value in node[start]:
        table[end] = min( table[start]+value , table[end] )

    index = sorted( [ (index,table[index]) for index,visit in enumerate(visited) if not visit ] , key = lambda x:(x[1],x[0]) )[0][0]
    visited[index]=1
    start=index
    print(i,table,visited)

 

개선 다익스트라

---

여기서 조금만 더 생각해보면, 각 Level에서 최소 가중치인 Edge를 선택하여 구현하면 더 빠르게 구현이 가능하다.

• 이 때 최소 가중치를 빠르게 찾아주는 자료구조는 Heapq => O(ElogE)
• E.g) BOJ 1753번 - 최단 경로 ( 해설 )

1. Heapq에 ( 0,시작점 ) 추가

2. Heapq에서 거리가 가장 작은 원소를 선택, 최단 거리 Table에 있는 값과 다르면 넘어간다.

3. 움직일 Node를 V라고 할 때, V와 이웃한 Node들에 대해 최단 거리 Table 값보다 V를 거쳐가는 것이 더 작은 값을 가질 경우 테이블을 갱신하고 Heapq에 추가한다.

4. Heapq가 빌 때 까지 2,3번을 반복한다.