ch9.py

#최단 경로

#가장 짧은 경로를 찾는 알고리즘
#이미 상황에 맞는 효율적인 알고리즘이 이미 정립되어있음
#보통 그래프로 표현
#각 지점은 노드로 표현
#지점 간의 연결은 간선으로 표현
#컴공 학부 수준에서 사용되는 최단 거리 알고리즘은 '다익스트라 최단 경로 알고리즘', '플로이드 워셜', '벨만 포드 알고리즘'
#이 중 다익스트라 최단 경로와 플로이드 워셜 알고리즘 유형이 가장 많이 출제

#다익스트라 최단 경로 알고리즘
#그래프에서 여러 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
#'음의 간선'이 없을 때 정상 작동(음의 간선은 0보다 작은 값을 가지는 간선을 의미)
#GPS 소프트웨어 기본 알고리즘으로 채택
#매번 비용이 적은 노드를 선택하는 과정을 반복하기 때문에 그리디 알고리즘으로 분류

#1. 출발 노드를 설정
#2. 최단 거리 테이블을 초기화
#3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택
#4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
#5. 3.과 4.을 반복

#각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며 이를 계속 갱신
#매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인

#다익스트라 알고리즘 구현법은 2가지
#1. 구현하기 쉽지만 느린 코드
#2. 구현하기 까다롭지만 빠른 코드(이를 연습)

print('노드 N개 간선 M개')
N, M = map(int, input().split())

graph = []
print('~에서 ~로 이동하는 ~비용')
for i in range(M):
    graph.append(list(map(int, input().split())))

print(graph)

#최소 비용
cost = [int(1e9)] * (N+1)
cost[1] = 0

#방문 여부
mark = [0] * (N+1)
mark[0] = 1

def d_alg(n):
    mark[n] = 1
    for i in range(M):
        if graph[i][0] == n:
            cost[graph[i][1]] = min(cost[graph[i][1]], cost[n]+graph[i][2])

def min_sel():
    a = 0
    for i in range(N+1):
        if mark[i] == 0:
            if cost[i] < cost[a]:
                a = i
    return a

for i in range(1, N+1):
    n = min_sel()
    print(mark)
    print(n)

    d_alg(n)
    print(cost)

print(cost)

for i in range(1, N+1):
    print(cost[i])

#자체 평가 : 아이디어 토대로 직접해봄. Good