[알고리즘] 탐욕법 - 다익스트라 알고리즘 코드 (Greedy Approach - Dijkstra's Algorithm Code)

문제)

Description

교재와 강의자료를 참고하여 Algorithm 4.3 다익스트라 알고리즘의 구현을 완성하시오.

그래프의 입력은 간선의 집합으로 주어지며,

출력값은 그리디 알고리즘의 각 단계별로 touch 배열의 변화를 출력하고,

F 집합에 추가되는 간선을 순서대로 출력한다.

단, 출발 정점은 1번 정점으로 가정하였으므로,

이후로 주어지는 정점 번호에 대해서 1번 정점으로부터 해당 정점으로 가능 최단 경로를 출력한다.

Input

첫 줄에 정점의 개수 n, 간선의 개수 m이 주어진다.

두 번째 줄부터 다음과 같은 형태로 m 개의 간선이 주어진다.

u v w

u와 v는 정점의 번호이고, 1부터 n까지의 자연수로 표시한다.

w는 간선 <u, v>의 가중치이며, 양의 정수 값으로 주어진다.

이후에 정점의 개수 T가 주어진다.

이후에 T개의 정점 번호가 주어진다.

(1번 정점이 주어지는 경우는 없다고 가정해도 된다)

Output

다익스트라 알고리즘의 초기 단계부터 종료 단계까지(n-1 times)

touch 배열의 값을 한 단계에 한 줄씩 출력한다.

첫번째 정점(v1)이 출발 정점이므로

touch 배열의 값은 2번부터 n번까지만 출력한다. (i = 2 .. n)

이후로, 다익스트라 알고리즘의 F 집합에 포함되는 간선을 순서대로 출력한다.

이후로, T개의 정점 v에 대해서

1번 정점으로부터 정점 v로 가는 최단 경로를 출력한다.

Sample Input 1

5 8
1 2 7
1 3 4
1 4 6
1 5 1
3 2 2
3 4 5
4 2 3
5 4 1
4
2
3
4
5

Sample Output 1

1 1 1 1
1 1 5 1
4 1 5 1
4 1 5 1
4 1 5 1
1 5 1
5 4 1
1 3 4
4 2 3
1 5 4 2
1 3
1 5 4
1 5

 

코드)

import sys
input = sys.stdin.readline
INF = 9999


def path(p, touch, ver):
    if ver != 1:
        path(p, touch, touch[ver])
    p.append(ver)


def func():
    Y = [1]     # 초기의 Y는 출발 정점인 v_1임
    F = list()      # 간선 정보의 리스트
    touch = [1] * (vertex_num + 1)      # touch[i]로 가기 직전의 방문한 정점
    length = [INF] * (vertex_num + 1)       # v_1에서 v_i로 가는 최단 거리, 이미 최단 거리를 찾았으면 -1로 둔다. 그래야 cycle을 형성하는지 따로 확인 안 해도 됨

    print(*touch[2:], sep=' ')

    for i in range(1, vertex_num + 1):
        touch[i] = 1
        length[i] = M[1][i]

    for _ in range(vertex_num - 1):
        # 간선은 vertex_num - 1개 들어가야함
        min = INF
        min_idx = -1
        for i in range(2, vertex_num + 1):
            # 1에서 어디가 최단 거리인지 일단 찾음
            if 0 <= length[i] < min:
                min = length[i]
                min_idx = i

        Y.append(min_idx)       # 일단은 1 다음으로 얘가 추가됨
        F.append((touch[min_idx], min_idx, M[touch[min_idx]][min_idx]))        # touch[min_idx]에서의 min_idx까지의 간선 정보

        for i in range(2, vertex_num + 1):
            if length[i] > length[min_idx] + M[min_idx][i]:
                length[i] = length[min_idx] + M[min_idx][i]
                touch[i] = min_idx

        length[min_idx] = -1

        print(*touch[2:], sep=' ')



    for i in range(len(F)):
        # F에 저장된 간선의 정보를 출력함
        print(*F[i], sep=' ')

    case = int(input())
    p = list()      # 경로를 저장하는 리스트
    for _ in range(case):
        end_vertex = int(input())

        path(p, touch, end_vertex)        # 경로를 찾음

        print(*p, sep=' ')
        p.clear()


vertex_num, edge_num = map(int, input().split())        # 정점의 개수와 간선의 개수를 입력받음
M = [[INF] * (vertex_num + 1) for _ in range(vertex_num + 1)]       # 인접 행렬을 만듬
for i in range(1, vertex_num):
    # 본인에게 가는 가중치는 0
    M[i][i] = 0

for _ in range(edge_num):
    # 입력받은 가중치로 초기화
    i, j, weight = map(int, input().split())    
    M[i][j] = weight


func()