❓문제
https://www.acmicpc.net/problem/11657
❗문제 정리
- 벨만 포드 알고리즘
: 음의 간선 순환을 사용하므로 다익스트라 사용불가. 다익스트라 사용시, 음의 순환으로 인해 -무한대로 빠져버림. 벨만 포드는 옵티멀한 최단 거리 알고리즘이나, 방문하지 않은 노드만 보던 다익스트라와 달리, 매번 모든 노드를 보므로 시간복잡도가 높음.
📑코드
n,m=map(int, input().split())# #노드, #간선
graph=[]#모든 간선에 대한 정보 담는 리스트만들기
for _ in range(m):
a,b,c=map(int, input().split())
graph.append((a,b,c))# (시작노드,도착노드, 거리)
INF=int(1e9)
distance=[INF]*(n+1)
#벨만포드 알고리즘
def bf(start):
distance[start]=0#시작 노드에 대해 초기화
for i in range(n):#전체 노드수-1만큼의 반복
for j in range(m):
depart=graph[j][0]
next=graph[j][1]
cost=graph[j][2]
#현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧을
if distance[depart]!=INF and distance[next]>distance[depart]+cost:
distance[next]=distance[depart]+cost
if i==n-1:
return True#음의 순환있음
return False#음의 순환없음
negative_cycle=bf(1)#시작 노드 1번에 대해 bf수행
if negative_cycle:#음의 순환이 있다면
print(-1)
else:#음의 순환이 없다면 1번 노드 제외한 다른 distance테이블 출력
for i in range(2, n+1):
if distance[i]!=INF:
print(distance[i])
else:
print(-1)📝코드 설명
- 필요한 인수 받고 최단 거리 테이블 제작
n,m=map(int, input().split())# #노드, #간선
graph=[]#모든 간선에 대한 정보 담는 리스트만들기
for _ in range(m):
a,b,c=map(int, input().split())
graph.append((a,b,c))# (시작노드,도착노드, 거리)
INF=int(1e9)
distance=[INF]*(n+1)
n(int) :노드 수 , m(int) : 간선 수
graph : 모든 간선에 대한 정보를 담는 리스트
(시작노드, 도착노드, 사이거리)를 graph에 넣기
최단 거리 테이블 distance를 노드수+1크기의 INF로 채워진 리스트 만듦.
- 벨만 포드 알고리즘
def bf(start):
distance[start]=0#시작 노드에 대해 초기화
for i in range(n):#전체 노드수-1만큼의 반복
for j in range(m):
depart=graph[j][0]
next=graph[j][1]
cost=graph[j][2]
#현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧을
if distance[depart]!=INF and distance[next]>distance[depart]+cost:
distance[next]=distance[depart]+cost
if i==n-1:
return True#음의 순환있음
return False#음의 순환없음음의 순환이 있냐 없냐를 리턴해줌.
- 벨만 포드 알고리즘 수행 및 결과 출력
negative_cycle=bf(1)#시작 노드 1번에 대해 bf수행
if negative_cycle:#음의 순환이 있다면
print(-1)
else:#음의 순환이 없다면 1번 노드 제외한 다른 distance테이블 출력
for i in range(2, n+1):
if distance[i]!=INF:
print(distance[i])
else:
print(-1)시작노드에 대해 벨만포드 알고리즘을 실행하고 그 결과를 음의 순환여부를 따지는 negative_cycle(boolean)에 넣는다.
이때, 음의 순환이 있으면(문제에 주어진, 어떤 도시로 가는 과정에서 시간을 무한히 오래전으로 되돌릴 수 있다면) -1을 출력.
음의 순환이 없는 경우, 최단 거리 테이블의 값을 출력한다. 음의 순환이 없지만, INF값을 지닌 경우(문제에 주어진, 해당 도시로 가는 경로가 없다면) -1을 출력한다.
이때, 시작지점->시작지점의 거리는 0이므로, 시작지점 노드 다음번째 노드부터 출력한다.
예제 1의 경우
1) i==0
2)i==1
3)i==2
🎖제출 결과
💡insight
AI dev