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

다익스트라: 최단경로 탐색 알고리즘

• 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 찾는대 사용됨
• 단 음수인 경우 사용못함
• 그 전에 구한 최단거리 정보를 그대로 사용한다는 점이 DP와 유사하다(DP개념에 다익스트라가 들어있는게 맞는듯)
• 정렬을 사용하기 때문에 그리디 알고리즘에 포함되기도 한다.

 

알고리즘 순서

1. 출발 노드를 설정한다(대체로 문제에서 주어질 수 있음)
2. 출발 노드를 기준으로 각 노드의 최소비용(최단거리)을 저장한다.
3. 방문하지 않은 노드중 가장 비용이 적은 노드를 선택한다.
4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소비용(최단거리)를 갱신한다
5. 3,4번을 반복한다

 

이에 예제를 적자면..

N = int(input()) # 노드 수
start = int(input()) # 시작 노드
E = int(input()) # 간선 수
edges = [list(map(int, input().split())) for _ in range(E)] # 출발 노드, 목적 노드, 가중치
lst = [[0] * N for _ in range(N)] # 인접 행렬
inf = 999 # 바로 갈 수 없는 경우

for i in range(E): # 간선 및 가중치 표시
    lst[edges[i][0]][edges[i][1]] = edges[i][2]

for i in range(N): # 나머지 인접 행렬 갈 수 없음으로 채우기
    for j in range(N):
        if not lst[i][j]:
            lst[i][j] = inf

for i in range(N): # 자기 자신은 0 표시
    lst[i][i] = 0

used = [0] * N # 경유지 사용했음을 표시
res = lst[start][:] # 시작 노드에서 모든 목적지까지의 비용
used[start] = 1 # 시작 노드는 경유지로 삼지 않기 위해 표시

for i in range(N - 1): # 하나씩 경유지로 삼기 시작
    via_min = inf
    via = 0 # 경유지 인덱스 찾기
    for j in range(N): # 아직 경유한 적 없으면서 현재의 비용 중 최소인 인덱스를 경유지로 채택
        if not used[j] and res[j] < via_min:
            via = j
            via_min = res[j]
    used[via] = 1 # 경유지 표시
    for j in range(N): # 기존의 최솟값과 경유지를 거친 값 비교해서 경유지 거진 값이 더 작을 경우 대체
        if res[j] > res[via] + lst[via][j]:
            res[j] = res[via] + lst[via][j]

print(*res)

---

INPUT은..

5
0
7
0 1 3
0 3 9
0 4 5
1 2 7
1 4 1
2 3 1
4 2 1

결과가 0 3 5 6 4 이 나온다면 성공