하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 문제이다. O(ElogV), 간선들은 모두 양의 값을 가져야 한다. (현실에 적용 가능하다.)
모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제, O(V^3)
점화식만 기억한다면 큰 어려움 없이 구현 가능하다.
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
첫째 줄에 도시의 개수 n, 통로의 개수 m, 메시지를 보내고자 하는 도시가 주어진다.
둘째 줄부터 m+1번째 줄에 통로에 대한 정보 x, y, c가 주어진다. 이는 특정 도시 x에서 다른 도시 y로 이어지는 통로가 있으며, 메시지가 전달되는 시간이 c라는 의미이다.
(x -> y 인 통로는 있지만, y -> x 인 통로는 없다면 y 는 x로 메시지를 보낼 수 없다.)
출력: 메시지를 보내고자 하는 도시에서 보낸 메시지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분해서 출력한다.
입력 예시
3 2 1
1 2 4
1 3 2
출력 예시
2 4
import heapq
INF = int(1e9) # 10억, 무한을 의미한다
def dijkstra(start, graph, dist):
dist[start] = 0
heap = []
heapq.heappush(heap, [0, start]) # 시작 노드로 가기 위한 최단경로는 0으로 설정하여 최소힙에 삽입
while heap:
cost, node = heapq.heappop(heap) # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
if dist[node] < cost:
continue
for c, n in graph[node]: # 현재 노드와 연결된 인접 노드들 확인
if cost + c < dist[n]: # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
dist[n] = cost + c
heapq.heappush(heap, [cost+c, n])
n, m ,start = map(int, input().split()) # 노드의 개수, 간선의 개수, 시작노드
road = [list(map(int, input().split())) for _ in range(m)]
graph = [[] for _ in range(n+1)] # 각 노드에 연결되어 있는 노드에 대한 정보를 담을 리스트
dist = [INF] * (n+1) # 최단 거리 테이블 모두 무한으로 시작
for r in road:
x,y,c = r
graph[x].append([c, y]) # x번 노드 -> y번 노드로 가는 비용 c
dijkstra(start, graph, dist)
city = [d for d in dist if d != INF and d != 0]
print(len(city), max(city), end = " ")
연습문제
import sys
import heapq
INF = (1e9)
def dijkstra(start, graph, dist):
dist[start] = 0
heap = []
heapq.heappush(heap, [0, start])
while heap:
cost, node = heapq.heappop(heap)
if dist[node] < cost:
continue
for c, n in graph[node]:
if cost + c < dist[n]:
dist[n] = cost + c
heapq.heappush(heap, [cost + c, n])
n, m, k, start = map(int, sys.stdin.readline().split()) #도시개수, 도로개수, 거리정보, 출발도시
dist = [INF] * (n+1) # 1번 도시는 index 1번 2번 도시는 index 2번 ...
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
graph[a].append([1, b])
dijkstra(start, graph, dist)
cnt = 0
for i in range(1, n+1):
if dist[i] == k:
cnt += 1
print(i)
if cnt == 0:
print(-1)
import heapq
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
INF = int(1e9)
cnt = 0
while True:
n = int(input())
if n == 0:
exit()
cnt += 1
cave = [[INF]*(n) for _ in range(n)]
board = [list(map(int, input().split())) for _ in range(n)]
heap = []
heapq.heappush(heap, (board[0][0], (0,0)))
cave[0][0] = board[0][0]
while heap:
cost, xy = heapq.heappop(heap)
x, y = xy
if cave[x][y] < cost:
continue
for dir in range(4):
nx, ny = x + dx[dir], y + dy[dir]
if 0 <= nx < n and 0 <= ny < n:
if cost + board[nx][ny] < cave[nx][ny]:
cave[nx][ny] = cost + board[nx][ny]
heapq.heappush(heap, (cost+board[nx][ny], (nx, ny)))
print('Problem {}: {}'.format(cnt, cave[n-1][n-1]))
from collections import deque
import heapq
dx = [0, 1, 0, -1]
dy = [-1, 0 ,1, 0]
INF = int(1e9)
T = int(input())
while T:
T -= 1
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF] * (n) for _ in range(n)]
heap = []
dist[0][0] = board[0][0]
heapq.heappush(heap, ([0,0], dist[0][0]))
while heap:
xy, cost = heapq.heappop(heap)
curX, curY = xy
if dist[curX][curY] < cost:
continue
for dir in range(4):
nx, ny = curX + dx[dir], curY + dy[dir]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if cost + board[nx][ny] < dist[nx][ny]:
heapq.heappush(heap, ([nx, ny], cost + board[nx][ny]))
dist[nx][ny] = cost + board[nx][ny]
print(dist[n-1][n-1])
input:
2
3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
output:
20
19
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[INF]*(n+1) for _ in range(n+1)]
# 현재 위치에서 현재 위치로 이동은 0
for i in range(1, n+1):
graph[i][i] = 0
# a에서 b로 가는 비용은 c 라고 설정
for _ in range(1, m+1):
a, b, c = map(int, input().split())
graph[a][b] = min(graph[a][b], c)
# 플로이드
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
# 이동 불가능인 경우 0으로 수정
for i in range(1,n+1):
for j in range(1, n+1):
if graph[i][j] == INF:
graph[i][j] = 0
for i in range(1,n+1):
for j in range(1, n+1):
print(graph[i][j], end=' ')
print()