그래프 - 최단 경로

• 최단 경로 정의 

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

 

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

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

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

 

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

음의 가중치 허용

 

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

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

 

 

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

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

 

시작정점에서 끝정점까지의 최단 경로에 정점 x가 존재.

이때, 최단 경로는 시작정점에서 끝정점까지의 최단 경로와 x에서 t까지의 최단경로 구성.

 

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

 

def dijkstra(u):
    # 시작 셋팅
    D[u] = 0

    # 정점 갯수 만큼 반복
    for i in range(V):
        # 가중치 최솟값 찾기
        min_v = 987654321
        for j in range(V):
            if visit[j] == 0 and min_v > D[j]:
                min_v = D[j]
                u = j

        # 방문 처리
        visit[u] = 1


        # 인접한 정점 업데이터
        for v in range(V):
            if adj[u][v] != 0 and visit[v] == 0 and D[v] > D[u] + adj[u][v]:
                D[v] = D[u] + adj[u][v]


V, E = map(int,input().split())
# 인접 행렬
adj = [[0] * V for _ in range(V)]
# 가중치
D = [987654321] * V
# 방문 여부
visit = [0] * V

# 입력
for i in range(E):
    s, e, w = map(int,input().split())
    adj[s][e] = w
    adj[e][s] = w

dijkstra(0)
print(D)