[python] 다익스트라 알고리즘_전보
9-1.py 다익스트라 알고리즘 소스코드
import sys
imput = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
graph = [false] * (n+1)
distance = [INF] * (n+1)
for _ in range(m):
a, b, c = map(int, input().split())
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 visited[i]:
min_value = distance[i]
index = i
return index
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_node()
visited[now] = True
for j in graph[now]:
cost = distance[now] + j[1]
if cost < distance[j[0]]:
distance[j[0]] = cost
dijkstra(start)
for i in range(1, n+1)
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])
Q1. 전보
어떤 나라에는 N개의 도시가 있다. 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어있어야한다. 예를 들어 X에서 Y로 향하는 통로는 있지만 Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정한 시간이 소요된다.
어느날 C라는 도시에서 위급상황이 발생했다. 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐 최대한 많이 퍼져나가야한다. 각 도시의 번호와 통로가 설치되어있는 정보가 주어졌을때 도시 C에서 보낸 메시지를 받게되는 도시의 개수는 총 몇개이며, 도시들이 모두 메시지를 받는데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성하시오.
*입력조건
- 첫째줄에 도시의 갯수N, 통로의 갯수 M, 메시지를 보내고자 하는 도시C가 주어진다.
(1<=N<=30,000, 1<=M<=200,000, 1<=C<=N)
-둘째줄부터 M+1번째 줄에 걸쳐서 통로에 대한 정보 X,Y,X가 주어진다. 이는 특정 도시 X에 다른 특정 도시 Y로 이어지는 통로가 있으며 메시지가 전달되는 시간이 Z라는 의미이다.
(1=X,Y<=N, 1<=Z<=10,000)
*출력조건
- 첫째줄에 도시 C에서 보낸 메시지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분하여 출력한다.
입력 예시
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
출력 예시
0
2
3
1
2
4
[문제 아이디어]
한 도시에서 다른 도시까지의 최단거리 문제를 묻는 문제이다.
이때 N,M의 범위가 크기 때문에
힙을 사용한 다익스트라알고리즘으로 해결해야한다.
import heapq
inport sys
input = sys.stdin.readline
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):
x, y, z = map(int, input().split())
graph[x].append((y, z))
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]))
dijkstra(start)
count = 0
max_distance = 0
for d in distance:
if d != INF:
count += 1
max_distance = max(max_distance, d)
print(count - 1, max_distance)
(해설)
import heapq
import sys
input = sys.stdin.readline # 빠른 입력
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정
# 노드의 개수, 간선의 개수, 시작노드를 입력받기
n, m, start = map(int, input().split())
# 최단거리 테이블
distance = [INF]*(n+1)
# 노드 연결정보
graph = [[] for i in range(n+1)]
for _ in range(m):
# x번 노드에서 y번 노드로 가는 비용 z
x,y,z = map(int, input().split())
graph[x].append((y,z))
# 다익스트라 알고리즘(최소힙 이용))
def dijkstra(start):
q=[]
# 시작 노드
heapq.heappush(q, (0,start))
distance[start] = 0
while q:
# 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
# 이미 처리된 노드였다면 무시
# 별도의 visited 테이블이 필요없이 최단거리테이블을 이용해 방문여부 확인
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)
count = 0
max_distance = 0
for d in distance:
if d != INF:
count += 1
max_distance = max(max_distance, d)
## 시작노드는 제외해야함으로 count-1
print(count - 1, max_distance)
ps) 다익스트라 알고리즘 너무 어렵다...!!!ㅠㅠ
Author And Source
이 문제에 관하여([python] 다익스트라 알고리즘_전보), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dmsql698/python-다익스트라-알고리즘전보저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)