최단 경로 찾기 (다익스트라 알고리즘)

최단 경로(Shortest Path) 찾기

주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로

다익스트라(Dijkstra) 알고리즘

최단 경로를 찾는 가장 대표적인 알고리즘

주어진 출발점에서 시작

출발점으로부터 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정

 

 

참고) 알기 쉬운 알고리즘

 

1.

출발점(s) = 서울

D[s] = 0으로 초기화 (여기서 D[v]는 출발점 s로부터 점 v까지의 거리를 저장하는 배열)

s를 제외한 D[v] = ∞로 초기화

트리(T)에는 최단 거리가 확정된 지점 저장, 처음에는 T = [출발점(s)]로 초기화

 

(각 지점v의 인덱스 순서가 아래와 같다고 가정)

D = [서울, 천안, 원주, 강릉, 논산, 대전, 대구, 포항 광주, 부산]

D = [0(서울), ∞(천안), ∞(원주), ∞(강릉), ∞(논산), ∞(대전), ∞(대구), ∞(포항), ∞(광주), ∞(부산)]

T = [서울]

 

 

2.

Vmin(확정된 지점까지의 최단 경로) + D[v] 값 < 기존의 D[v] 값 일 때 D[v]를 Vmin + D[v]값으로 업데이트

서울과 이어진 천안과 원주의 경로를 구할 것

 

천안의 경우 기존 D[천안] = ∞

Vmin(확정된 지점까지의 최단 경로; 서울에서 서울) + D[천안](가중치그래프에서 확인가능한 가중치값) = 0 + 12 = 12

12 < ∞ 참이므로 D[천안]을 12로 업데이트

D = [0(서울), 12(천안), ∞(원주), ∞(강릉), ∞(논산), ∞(대전), ∞(대구), ∞(포항), ∞(광주), ∞(부산)]

 

원주의 경우 기존 D[원주] = ∞

Vmin(확정된 지점까지의 최단 경로; 서울에서 서울) + D[원주](가중치그래프에서 확인가능한 가중치값) = 0 + 15 = 15

15 < ∞ 참이므로 D[원주]을 15로 업데이트

D = [0(서울), 12(천안), 15(원주), ∞(강릉), ∞(논산), ∞(대전), ∞(대구), ∞(포항), ∞(광주), ∞(부산)]

참고) 알기 쉬운 알고리즘

 

트리에 없는 점들 중 가장 작은 D값을 가진 지점을 트리에 추가

T = [서울, 천안]

 

 

3.

트리의 마지막에 추가된 천안을 기준으로 천안과 이어진 논산과 대전의 경로를 구할 것

 

논산의 경우 기존 D[논산] = ∞

Vmin(확정된 지점까지의 최단 경로; 서울에서 천안) + D[논산](가중치그래프에서 확인가능한 가중치값) = 12 + 4 = 16

16 < ∞ 참이므로 D[논산]을 16으로 업데이트

D = [0(서울), 12(천안), 15(원주), ∞(강릉), 16(논산), ∞(대전), ∞(대구), ∞(포항), ∞(광주), ∞(부산)]

 

대전의 경우 기존 D[대전] = ∞

Vmin(확정된 지점까지의 최단 경로; 서울에서 천안) + D[대전](가중치그래프에서 확인가능한 가중치값) = 12 + 10 = 22

22 < ∞ 참이므로 D[대전]을 22로 업데이트

D = [0(서울), 12(천안), 15(원주), ∞(강릉), 16(논산), 22(대전), ∞(대구), ∞(포항), ∞(광주), ∞(부산)]

참고) 알기 쉬운 알고리즘

 

트리에 없는 점들 중 가장 작은 D값을 가진 지점을 트리에 추가

T = [서울, 천안, 원주]

 

 

4.

트리의 마지막에 추가된 원주를 기준으로 원주와 이어진 대구와 강릉의 경로를 구할 것

 

대구의 경우 기존 D[대구] = ∞

Vmin(확정된 지점까지의 최단 경로; 서울에서 원주) + D[대구](가중치그래프에서 확인가능한 가중치값) = 15 + 7 = 22

22 < ∞ 참이므로 D[대구]을 22로 업데이트

D = [0(서울), 12(천안), 15(원주), ∞(강릉), 16(논산), 22(대전), 22(대구), ∞(포항), ∞(광주), ∞(부산)]

 

강릉의 경우 기존 D[강릉] = ∞

Vmin(확정된 지점까지의 최단 경로; 서울에서 원주) + D[강릉](가중치그래프에서 확인가능한 가중치값) = 15 + 21 = 36

36 < ∞ 참이므로 D[강릉]을 36으로 업데이트

D = [0(서울), 12(천안), 15(원주), 36(강릉), 16(논산), 22(대전), 22(대구), ∞(포항), ∞(광주), ∞(부산)]

참고) 알기 쉬운 알고리즘

 

트리에 없는 점들 중 가장 작은 D값을 가진 지점을 트리에 추가

T = [서울, 천안, 원주, 논산]

 

 

5.

트리의 마지막에 추가된 논산을 기준으로 논산과 이어진 광주와 대전의 경로를 구할 것

 

광주의 경우 기존 D[광주] = ∞

Vmin(확정된 지점까지의 최단 경로; 서울에서 논산) + D[광주](가중치그래프에서 확인가능한 가중치값) = 16 + 13 = 29

29 < ∞ 참이므로 D[광주]을 29로 업데이트

D = [0(서울), 12(천안), 15(원주), 36(강릉), 16(논산), 22(대전), 22(대구), ∞(포항), 29(광주), ∞(부산)]

 

대전의 경우 기존 D[대전] = 22

Vmin(확정된 지점까지의 최단 경로; 서울에서 논산) + D[대전](가중치그래프에서 확인가능한 가중치값) = 16 + 3 = 19

19 < 22 참이므로 D[대전]을 19로 업데이트

D = [0(서울), 12(천안), 15(원주), 36(강릉), 16(논산), 19(대전), 22(대구), ∞(포항), 29(광주), ∞(부산)]

참고) 알기 쉬운 알고리즘

 

트리에 없는 점들 중 가장 작은 D값을 가진 지점을 트리에 추가

T = [서울, 천안, 원주, 논산, 대전]

 

 

6.

트리의 마지막에 추가된 대전을 기준으로 대전과 이어진 대구의 경로를 구할 것

 

기존 D[대구] = 22

Vmin(확정된 지점까지의 최단 경로; 서울에서 대전) + D[대구](가중치그래프에서 확인가능한 가중치값) = 19 + 10 = 29

29 < 22 거짓이므로 D[대구]를 업데이트하지 않고 그대로 두기

D = [0(서울), 12(천안), 15(원주), 36(강릉), 16(논산), 19(대전), 22(대구), ∞(포항), 29(광주), ∞(부산)]

참고) 알기 쉬운 알고리즘

 

트리에 없는 점들 중 가장 작은 D값을 가진 지점을 트리에 추가

T = [서울, 천안, 원주, 논산, 대전, 대구]

 

 

7.

트리의 마지막에 추가된 대구를 기준으로 대구와 이어진 부산과 포항의 경로를 구할 것

 

부산의 경우 기존 D[부산] = ∞

Vmin(확정된 지점까지의 최단 경로; 서울에서 대구) + D[부산](가중치그래프에서 확인가능한 가중치값) = 22 + 9 = 31

31 < ∞ 참이므로 D[부산]을 31로 업데이트

D = [0(서울), 12(천안), 15(원주), 36(강릉), 16(논산), 19(대전), 22(대구), ∞(포항), 29(광주), 31(부산)]

 

포항의 경우 기존 D[포항] = ∞

Vmin(확정된 지점까지의 최단 경로; 서울에서 대구) + D[포항](가중치그래프에서 확인가능한 가중치값) = 22 + 19 = 41

41 < ∞ 참이므로 D[포항]을 41로 업데이트

D = [0(서울), 12(천안), 15(원주), 36(강릉), 16(논산), 19(대전), 22(대구), 41(포항), 29(광주), 31(부산)]

참고) 알기 쉬운 알고리즘

 

트리에 없는 점들 중 가장 작은 D값을 가진 지점을 트리에 추가

T = [서울, 천안, 원주, 논산, 대전, 대구, 광주]

 

 

8.

트리의 마지막에 추가된 광주를 기준으로 광주와 이어진 부산의 경로를 구할 것

 

기존 D[부산] = 31

Vmin(확정된 지점까지의 최단 경로; 서울에서 광주) + D[부산](가중치그래프에서 확인가능한 가중치값) = 29 + 15 = 44

44 < 31 거짓이므로 D[부산]을 업데이트하지 않고 그대로 두기

D = [0(서울), 12(천안), 15(원주), 36(강릉), 16(논산), 19(대전), 22(대구), 41(포항), 29(광주), 31(부산)]

 

트리에 없는 점들 중 가장 작은 D값을 가진 지점을 트리에 추가

T = [서울, 천안, 원주, 논산, 대전, 대구, 광주, 부산]

 

 

9.

트리의 마지막에 추가된 부산을 기준으로 부산과 이어진 포항의 경로를 구할 것

 

기존 D[포항] = 41

Vmin(확정된 지점까지의 최단 경로; 서울에서 부산) + D[포항](가중치그래프에서 확인가능한 가중치값) = 31 + 5 = 36

36 < 41 참이므로 D[포항]을 36으로 업데이트

D = [0(서울), 12(천안), 15(원주), 36(강릉), 16(논산), 19(대전), 22(대구), 36(포항), 29(광주), 31(부산)]

참고) 알기 쉬운 알고리즘

 

트리에 없는 점들 중 가장 작은 D값을 가진 지점을 트리에 추가

(동일한 D값일때는 인덱스값이 작은 걸 우선으로 트리에 추가)

T = [서울, 천안, 원주, 논산, 대전, 대구, 광주, 부산, 강릉]

 

 

10.

트리의 마지막에 추가된 강릉을 기준으로 강릉과 이어진 포항의 경로를 구할 것

 

기존 D[포항] = 36

Vmin(확정된 지점까지의 최단 경로; 서울에서 강릉) + D[포항](가중치그래프에서 확인가능한 가중치값) = 36 + 25 = 61

61 < 36 거짓이므로 D[포항]을 업데이트하지 않고 그대로 두기

D = [0(서울), 12(천안), 15(원주), 36(강릉), 16(논산), 19(대전), 22(대구), 36(포항), 29(광주), 31(부산)]

참고) 알기 쉬운 알고리즘

 

트리에 없는 점들 중 가장 작은 D값을 가진 지점을 트리에 추가

T = [서울, 천안, 원주, 논산, 대전, 대구, 광주, 부산, 강릉, 포항]

 

 

def get_min_vertex(D, T):
    vmin = -1
    mindist = float('inf')
    for v in range(len(D)):
        # T라는 Array 안에 v가 있나없나를 검사
        # T안에 있다는 건 이미 사용했다는 거니까 T에 없는 점들에 대해서만 최솟값을 구하면 됨
        # T라는 배열에 v가 없으면 안쓴 점이니까 최솟값찾기
        if not v in T and D[v] < mindist:
            mindist = D[v]
            vmin = v
    
    return vmin



def shortest_path_dijkstra(V, adj, start):
    # 배열 D를 무한대로 초기화
    # 1. start의 D[s]는 0 으로 초기화
    # 2. 배열 D에서 최솟값을 찾아서 Vmin에 저장
    # 3. 
    
    vsize = len(V)
    # T = [start]
    T = []
    D = [float('inf')] * vsize  # D는 맨 처음 모두 무한대로 초기화
    P = [start] * vsize     # 나중에 출력할 때 지역명이 나오도록
    
    D[start] = 0
    
    for i in range(vsize):
        if adj[start][i] is not None:
            D[i] = adj[start][i]
            
    while len(T) < vsize:
        vmin = get_min_vertex(D, T)
        T.append(vmin)
        for u in range(vsize):      # weight update
            if u not in T and adj[vmin][u] is not None and (D[vmin] + adj[vmin][u]) < D[u]:
                D[u] = D[vmin] + adj[vmin][u]
                P[u] = vmin     # 최소거리를 가졌을 때 그 상대 지역이 어딘지 저장
                print(D)
                
    return P, D
    



# 실행
if __name__ == '__main__':
    vertex = ['서울', '천안', '원주', '강릉', '논산', '대전', '대구', '포항', '광주', '부산']
    weight = [  [None,    12,    15,  None,  None,  None,  None,  None,  None,  None],  # 서울
                [  12,  None,  None,  None,     4,    10,  None,  None,  None,  None],  # 천안
                [  15,  None,  None,    21,  None,  None,     7,  None,  None,  None],  # 원주
                [None,  None,    21,  None,  None,  None,  None,    25,  None,  None],  # 강릉
                [None,     4,  None,  None,  None,     3,  None,  None,    13,  None],  # 논산
                [None,    10,  None,  None,     3,  None,    10,  None,  None,  None],  # 대전
                [None,  None,  None,  None,  None,    10,  None,    19,  None,     9],  # 대구
                [None,  None,     7,    25,  None,  None,    19,  None,  None,     5],  # 포항
                [None,  None,  None,  None,    13,  None,  None,  None,  None,    15],  # 광주
                [None,  None,  None,  None,  None,  None,     9,     5,    15,  None]]  # 부산
    
    # print("\nDijkstra Shortest Path....")
    # print(path)
    shortest_path_dijkstra(vertex, weight, 0)

 

실행 결과