최단 경로 - Dijkstra

최단 경로 정의

: 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로

 

 

 

하나의 시작 정점에서 끝 정점까지의 최단 경로

1) 다익스트라(dijkstra) 알고리즘 

- 음의 가중치를 허용하지 않음

2) 벨만-포드(Bellman-Ford) 알고리즘

- 음의 가중치 허용

 

모든 정점들에 대한 최단 경로

1) 플로이드-워샬(Floyd-Warshall) 알고리즘

 

 

 

 

 

Dijkstra 알고리즘

: 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식

 

• 시작 정점에서 끝 정점까지의 최단 경로에 정점 x가 존재한다.
• 이때, 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단경로로 구성된다

 

탐욕 기법을 사용한 알고리즘으로 MST의 Prim 알고리즘과 유사

 

 

 

구현

'''
5 8
0 1 2
0 2 4
1 2 1
1 3 7
2 4 3
3 4 2
3 5 1
4 5 5
'''

def dijk():
    # 최단 경로를 담을 배열
    U = []
    # 선택된 간선의 가중치를 담을 배열
    D = [10000] * (N+1)
    P = [10000] * (N + 1)

    # 첫번째 노드를 선택할 수 있도록 함
    D[0] = 0

    while len(U) < (N+1):
        # D가 최선인 curV를 선택
        minV = 10000
        for i in range(N+1):
            if i in U : continue
            if minV > D[i]:
                minV = D[i]
                curV = i

        U.append(curV)

        # curV와 연결된 D의 값을 수정
        for i in range(N+1):

            if i in U : continue
            # curV 까지 누적된 가중치 + curV에서 선택된 정점 까지의 가중치
            if G[curV][i] and D[i] > D[curV]+G[curV][i]:
                D[i] = D[curV]+G[curV][i]
                P[i] = curV

    print(f'방문순서(U) : {U}')
    print(f'선택된 간선의 가중치(D) : {D}')
    print(f'연결된 노드의 인덱스(P) : {P}')


N, E = map(int, input().split())
# 인접 행렬
G = [[0] * (N+1) for _ in range(N+1)]

for _ in range(E):
    u, v, w = map(int, input().split())
    G[u][v] = w
    G[v][u] = w      # 가중치가 있는 무방향 그래프

dijk()


'''
방문순서(U) : [0, 1, 2, 4, 3, 5]
선택된 간선의 가중치(D) : [0, 2, 3, 8, 6, 9]
연결된 노드의 인덱스(P) : [10000, 0, 1, 4, 2, 3]
'''

 

 

 

 

 

록키 산맥 투어 이동 중에 잠깐 내려서 1분 만에 만든 눈사람들  _888_

 

이번 겨울에는 예쁜 눈이 내리는 날이 많았으면 좋겠어-