* 개선된 다익스트라 알고리즘*
- 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우 사용.
- '최단 거리가 가장 짧은 노드'를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식 사용.
import sys
input=sys.stdin.readline
import heapq # 우선순위 큐
INF=int(1e9) # 무한을 의미하는 값
n,m=map(int,input().split()) # 노드의 개수, 간선의 개수 입력
start=int(input()) # 시작 노드 입력
graph=[[] for i 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):
q=[]
heapq.heappush(q,(0,start)) # 시작노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
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]))
dijkstra(start)
for i in range(1,n+1):
if distance[i]==INF:
print('INFINITY')
else:
print(distance[i])
* 플로이드 워셜 알고리즘*
- 모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 경우 사용.
import sys
input=sys.stdin.readline
INF=int(1e9) # 무한을 의미하는 값
n=int(input()) # 노드의 개수 입력
m=int(input()) # 간선의 개수 입력
# 2차원 리스트 만들기
graph=[[INF]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,n+1):
if i==j:
graph[i][j]=0
# 간선에 대한 정보 입력받기
for _ in range(m):
a,b,c=map(int,input().split())
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])
for i in range(1,n+1):
for j in range(1,n+1):
if graph[i][j]==INF:
print("INFINITY",end=" ")
else:
print(graph[i][j],end=" ")
print()
01. 미래 도시
import sys
input=sys.stdin.readline
INF=int(1e9) # 무한을 의미하는 값
n,m=map(int,input().split()) # 노드, 간선 개수 입력
# 2차원 리스트 만들기
graph=[[INF]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,n+1):
if i==j:
graph[i][j]=0
# 간선에 대한 정보 입력받기
for _ in range(m):
a,b=map(int,input().split())
graph[a][b]=1
graph[b][a]=1
# k번 중간 방문 목표, x가 최종 목표
x,k=map(int,input().split())
# 플로이드 워셜 알고리즘 수행
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])
distance=graph[1][k]+graph[k][x]
if distance>=INF:
print(-1)
else:
print(distance)
02. 전보
import sys
input=sys.stdin.readline
import heapq # 우선순위 큐
INF=int(1e9) # 무한을 의미하는 값
n,m,start=map(int,input().split()) # 노드의 개수, 간선의 개수, 메세지 보내고자 하는 도시 입력
graph=[[] for i 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):
q=[]
heapq.heappush(q,(0,start)) # 시작노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
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]))
dijkstra(start)
city_count=0
time_count=0
for i in range(1,n+1):
if distance[i]!=INF:
city_count+=1
if time_count<distance[i]:
time_count=distance[i]
print(city_count-1, time_count)