다익스트라 알고리즘 - 최단경로

단일 시작점 최단 경로 알고리즘

시작점에서 가까운 순서대로 정점을 방문한다.

우선순위 큐를 사용, 큐에 정점의 번호화 함께 지금까지 찾아낸 정점까지의 최단거리를 쌍으로 넣고, 최단거리를 기준으로 정점을 배열한다. -> 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 가까운 점을 찾는다.

정점을 방문할 때마다 인접한 정점을 모두 검사한다.

음수 사이클이 없고 음수 간선이 있는 경우에 이용 가능하지만 시간 복잡도가 지수적으로 늘어나므로 권장하지 않는다.

시간복잡도

우선순위 큐에 따라 모든 간선은 한번씩 검사된다 -> O(간선수)

우선순위 큐가 가장 커지는 최악의 시나리오는, 모든 간선이 검사될 떄마다 모든 정점이 큐에 추가되는 것 -> 추가되는 최대 정점 수 -> O(간선수) , 원소 하나마다 추가, 삭제에 O(log간선수) -> O(간선수log간선수)

결국 O(간선수log간선수) or O(간선수log정점수)

우선순위 큐를 사용하지 않는 방법

• 정점의 수가 적거나 간선의 수가 매우 많은 경우에는 우선순위 큐를 사용하지 않는 것이 더 빠를 수 있다.
• 방문할 정점을 큐에 넣는 대신 매번 반복문을 이용해 방문하지 않은 정점 중 시작점에서 거리가 가장 작은 값을 찾는다.
• 각 정점의 방문을 배열에 저장해야함

---

코드

distance 에는 시작 정점으로부터의 최단 경로가 저장되고, visited 는 최단 경로가 밝혀졌는 지 확인하기 위한 일차원 배열이다.

알고리즘의 매 단계에서 방문하지 않은 정점 중 가장 distance 가 작은 정점을 visited 에 추가한다. 새로운 정점 u 가 visited에 추가되면 아직 방문하지 않은 남은 다른 정점들의 distance 값을 수정한다. (u를 거쳐서 정점까지 가는 거리와 기존의 거리를 비교)

int_max = 10001
max_dot = 7 # 정점의 수
weight = [[0,7,int_max,int_max,3,10,int_max], [7,0,4,10,2,6,int_max],[int_max,4,0,2,int_max,int_max,int_max],[int_max,10,2,0,11,9,4],[3,2,int_max,11,0,int_max,5],[10,6,int_max,9,int_max,0,int_max],[int_max,int_max,int_max,4,5,int_max,0]]

distance = [int_max for _ in range(max_dot)] # 시작 정점으로부터 최단 경로 거리
visited = [False for _ in range(max_dot)] # 방문한 정점 표시

# 아직 방문하지 않은(집합 S에 있지 않은) 정점들 중 가중치가 가장 적은 정점 반환
def newDot():
    m = int_max
    k = -1
    for i in range(max_dot): 
        if not visited[i]: 
            if m > distance[i]: 
                m = distance[i]
                k = i
    return k

def dijkstra():
    global visited
    global distance # 시작 정점으로부터의 최단 경로

    for i in range(max_dot):
        distance[i] = weight[0][i] # 기본 가중치로 초기화

    while not all(visited): # visited 가 모두 True 가 아닐때까지 == 모든 정점을 방문하기 전까지
        d = newDot() # 가중치가 가장 적은 정점을 가져와서
        visited[d] = True # 방문한 후 
        for j in range(max_dot): # 다른 정점들의 가중치를 갱신
            distance[j] = min(distance[j], distance[d] + weight[d][j])

dijkstra()
print(distance)