[ 이코테 ] 다익스트라 알고리즘

 

▶ 최소힙 & 최대힙

 

 

▶ 다익스트라 알고리즘

 

3번인 방문하지 않은 노드 중 짧은 노드를 찾을 때 최소힙을 이용해준다

 

 

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())

    #a번 노드에서 b번 노드로 가는 비용이 C라는 의미
    graph[a].append((b, c))

def dijkstra(start):
    queue = []

    #시작 노드로 가기 위한 최단 거리는 0으로 설정하고 queue에 넣는다
    heapq.heappush(queue, (0, start))
    distance[start] = 0

    while queue:
        # 최단 거리가 가장 짧은 노드의 정보를 뽑아낸다
        current_distance, current_node = heapq.heappop(queue)

        #현재 노드가 이미 처리된적 있다면 무시
        #(distance 리스트에 들어있는 값보다 현재 거리 값이 크다면 무시)
        if distance[current_node] < current_distance:
            continue

        #현재 노드와 인접하 노드들의 정보 확인
        for adjacent, weight in graph[current_node]:
            cost = current_distance + weight

            #distance리스트의 거리 보다 현재 노드를 거쳐서 다른 노드로 이동하는 경우가 더 짧은경우
            #거리값을 짧은 거리로 바꿔주고, heapq에 update해준다
            if cost < distance[adjacent]:
                distance[adjacent] = cost
                heapq.heappush(queue,(cost, adjacent))


dijkstra(start)

#모든 노드로 가기 위한 최단경로 출력
for i in range(1, n + 1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

 

 

▶ 플로이드 워셜

 

다익스트라와 다른점은 매 단계마다 최단거리 노드를 찾는 과정이 없다

그래서 삼중 반복문을 이용해서 2차원 테이블의 값을 업데이트 해준다 -> 시간복잡도 아주 높아서 보통 사용X

a에서 b로 가는 경로가 a -> b로 가는게 짧은지,

a -> k -> b로 가는게 짧은지 찾아서 테이블을 수정해주면 된다

 

 

 

▶ 전보

 

다익스트라를 이용해서 문제를 풀 수 있다.

C점에서 출발해서 모든 노드까지 가는 최단 거리를 구하고, 가장 멀리있는 거리를 구하면 된다

(메세지를 모두 받는데 걸린 시간 = 가장 멀리있는 거리)

 

import sys
import heapq

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

def dijkstra(start):
    queue = []
    heapq.heappush(queue, (0, start))
    distance[start] = 0

    while queue:
        now_distance, now_node = heapq.heappop(queue)

        if distance[now_node] < now_distance:
            continue

        for adjacent, weight in adj[now_node]:
            totalCost = now_distance + weight

            if totalCost < distance[adjacent]:
                distance[adjacent] = totalCost
                heapq.heappush(queue, (totalCost, adjacent))


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

for _ in range(m):
    x, y, z = map(int, input().split())
    adj[x].append((y, z))

dijkstra(start)

count = 0
maxDist = 0

for d in distance:
    if d != 1e9:
        count += 1
        maxDist = max(maxDist, d)

#시작 노드는 제외해야하므로 count - 1을 한다
print(count -1, maxDist)

 

 

 

▶ 미래 도시

 

 

INF = int(1e9)

n, m = map(int, input().split())
#2차원 배열을 만들어서, 모든 값을 무한으로 초기화한다
array =  [[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:
            array[a][b] = 0

#a에서 b로 가는 비용이 1이라는 의미
#양방향이라고 했기 때문에 아래와 같이 초기화해준다
for _ in range(m):
    a, b = map(int, input().split())
    array[a][b] = 1
    array[b][a] = 1

x, k = map(int, input().split())

for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            array[a][b] = min(array[a][b], array[a][k] + array[k][b])

distance = array[1][k] + array[k][x]

if distance >= INF:
    print(-1)
else:
    print(distance)

 

 

 

 

출처 : youtu.be/acqm9mM1P6o