#7 Python 코딩테스트 최단 경로 알고리즘

https://www.youtube.com/watch?v=acqm9mM1P6o&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7 

이 포스팅은 위의 영상을 보고 제가 필요하다고 생각된 부분을 정리한 포스팅입니다.

 

다익스트라 알고리즘

특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산

- 음의 간선이 없을 때 정상적으로 동작.

- 그리디 알고리즘에 속함.

위 상태에서 시작해서 매번 가장 짧은 길이의 노드를 찾아가며 큐에 추가

다익스트라 알고리즘 간단한 구현 방법

import sys
input = sys.stdin.readline
INF = int(ie9) # 무한을 의미하는 값으로 10억을 설정

n, m = map(int, input().split())
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n+1)]
# 방문한 적이 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (n + 1)
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b,c))

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
    min_value = INF
    index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
    for i in range(1, n + 1):
        if distance[i] < min_value and not not visited[i]:
            min_value = distance[i]
            index = i
        return index

def dijkstra(start):
    # 시작 노드 초기화
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        # start에서 갈 수 있는 노드들의 거리 정보 초기화
        distance[j[0]] = j[1]
        # 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
        for i in range(n - 1):
            # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
            now = get_smalleset_node()
            visited[now] = True
            # 현재 노드와 연결된 다른 노드를 확인
            for j in graph[now]:
                cost = distance[now] + j[1]
                # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
                if cost < distance[j[0]]:
                    distance[j[0]] = cost

dijkstra(strat)

for i in range(1, n + 1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

 

우선순위 큐 활용

최소 힙 구현

import heapq

# 오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h = []
    result = []
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

 

최대 힙 구현

import heapq

# 내림차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h = []
    result = []
    for value in iterable:
        heapq.heappush(h, -value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

다익스트라 알고리즘 개선된 구현 방법

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int,input.split())
start = int(input())
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)

for _ in range(m):
    a, b, c = map(int,input().split())
    graph[a].append((b, c))
    
def dijkstra(start):
    distance[start] = 0
    q = []
    heapq.heappush(q,(0, start))
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist: # 이미 더 작은 값으로 초기화 됐다면 (예전에 실행 된 것)
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q,(cost, i[0]))
dijkstra(start)

for i in range(1, n + 1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

 

플로이드 워셜 알고리즘

한 노드에서 직접 해당 노드로 가는 경우와 특정 노드를 거쳐가는 경우를 비교해 더 낮은 값으로 초기화함.

플로이드 워셜 알고리즘

INF = int(1e9)

n = int(input())
m = int(input())

graph= [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

for _ in range(m):
    # A에서 B로 가는 비용은 C 라고 설정
    a, b, c = map(int,input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
# k = 거처가는 노드, a = 출발지, b = 도착지
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if graph[a][b] == INF:
            print("INFINITY", end=" ")
        else:
            print(graph[a][b], end=" ")
    print()