604 최단경로

여기서의 비용은 간선의 크기,또는 가중치이라고 불린다.

다익스트라

• 양의 가중치여야함
• 안 방문한 노드중 가장 비용이 적은 간선을 선택
  • 방문한 노드는 최단거리가 확정이됨
• 특정지점에서 다른 노드들까지의 최단거리 1 to N
  • 출발노드 있음
• 일종의 📚 602 그리디

구현 방법

1. 배열 사용 $O(V^2)$

import math

input = sys.stdin.readline
n,m = map(int,input().split()) # 노드 개수,간선
start = int(input())
# 그래프에 대한 정보를 담는 노드
graph = [[] for i in range(n+1)]
visited = [False]*(n+1)
# 시작 노드에 대한 최단 거리를 저장하는 리스트
distance = [math.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():
    minV = math.inf
    node = 0 # 최단거리의 노드
    for i in range(1,n+1):
        if not visited[i] and distance[i]< minV:
            minV = distance[i]
            node = i
    return node

def dijkstra(start):
    distance[start] = 0
    visited[start] = True
    # 시작 노드와 연결된 노드의 거리를 입력
    for j in graph[start]:
        distance[j[0]]=j[1]
    for i in range(n-1):
        now = get_smallest()
        visited[now] = True
        # 가장 짧은 노드 꺼내서 다른 연결된 노드를 확인하고 거리를 업데이트한다
        for j in graph[now]:
            cost = distance[now] + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost

2. 우선순위큐(힙) 사용 $O(V(logV))$
   우선순위큐는 내부적으로 최소힙 최대힙을 이용한다.
   현재 가장 가까운 노드를 저장하기위해서 우선순위 큐사용
   위에서의 getsmallest의 함수가 필요없음

   import heapq
   # 그래프 입력 까지 같음
   def dijkstra(start):
       q = []
           # 거리, 노드로 입력받음
       heapq.heappush(q,(0,start))
       distance[start] = 0
       while q:
           dist, now = heapq.heappop(q)
           # 이전에 입력된 거리가 더 짧다 == 처리된 적이 있는 노드
           if distance[now] < dist:
               continue
           #인접한 노드확인
           for i in graph[now]:
               cost = dist + i[1]
               if cost < distance[i[0]] :
                   distance[i[0]] = cost
                   heapq.heappush(q,(cost,i[0]))
       
   

벨만포드

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

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 모든 간선에 대한 정보를 담는 리스트 만들기
edges = []
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    edges.append((a, b, c))

def bf(start):
    # 시작 노드에 대해서 초기화
    distance[start] = 0
    # 전체 n - 1번의 라운드(round)를 반복
    for i in range(n):
        # 매 반복마다 "모든 간선"을 확인하며
        for j in range(m):
            cur_node = edges[j][0]
            next_node = edges[j][1]
            edge_cost = edges[j][2]
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if distance[cur_node] != INF and distance[next_node] > distance[cur_node] + edge_cost:
                distance[next_node] = distance[cur_node] + edge_cost
                # n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
                if i == n - 1:
                    return True
    return False

# 벨만 포드 알고리즘을 수행
negative_cycle = bf(1) # 1번 노드가 시작 노드

if negative_cycle:
    print("-1")
else:
    # 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리를 출력
    for i in range(2, n + 1):
        # 도달할 수 없는 경우, -1을 출력
        if distance[i] == INF:
            print("-1")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(distance[i])

플로이드 워셜

• 모든지점에서 다른 모든지점까지의 최단경로 N to N
• 출발점이여러개다!! 플로이드워셜
• 시간 복잡도 $O(N^3)$
  • 3중반복문..
• 2차원배열로 자기자신은 0 없는 간선은 inf, 있는 간선은 값을 넣음
• a,b,c가 노드, a> b일대와 a> c , c> b일때 머가 더 가까운지 비교해서 기입.

import math
n,m = map(int, input().split())
# 이차원 배열
graph = [[math.inf] * (n+1) for _ in range(n+1)]

# 자기자신은 0으로
for a in range(1,n+1):
    graph[a][a] = 0

# 간선에 대한 정보 업데이트
for _ in range(m)
    a,b,c = map(int,input().split()) # 노드, 노드 ,비용
    graph[a][b] = c

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