🧚‍♂️알고리즘🧚‍♂️ - 그래프 - 벨만 포드

🧚‍♂️벨만-포드🧚‍♂️

특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색

 

"음수 가중치 에지" 가 있어도 수행 가능!

전체 그래프에서 "음수 사이클의 존재 여부" 판단 가능!

 

 

다익스트라는 음수 있으면 불가!!

세으니 추천글

[알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

---

1.   에지 리스트 이용해서 그래프를 구현하고 최단 경로 리스트(결과) 초기화

 

2. 모든 에지를 확인해 정답 리스트 업데이트하기

노드 개수 -1 만큼 업데이트 진행 ( 두 노드 사이 거리는 "노드 개수 -1" 이 최대이기 때문)

'종료노드의 결과 리스트값'이 '시작 노드의 결과 리스트값' + '가중치'보다 클 때 이 값으로 새로 업데이트.

 

3. 음수 사이클 유무 확인하기

모든 에지를 한번씩 다시 사용해 업데이트되는 노드가 발생하는지 확인.

발생시 "무한하게 돌수록 가중치가 계속 감소하는 음수 사이클"이 있다는 뜻이므로 최단 거리 판별 풀가.

---

🥇골드 4 ( 정석문제인듯 )

11657번: 타임머신

타임머신 가동 가능이라서 시간이 음수 값으로 걸릴 때가 있음(음수 가중치 에지)

시간을 무한이 오래 전으로 되돌릴 수 있다면 ( 최단 시간 찾기 불가)

=> 벨만-포드 알고리즘 사용

for s,e,t, in edges:

여러 값 든 리스트 이렇게 빼낼 수 있음!!!

import sys
N,M = map(int,sys.stdin.readline().split()) #노드/에지
edges =[] # 에지리스트
distance = [sys.maxsize] *(N+1) #거리 결과리스트

for _ in range(M):
    s,e,t = map(int,sys.stdin.readline().split()) #시작노드/끝노드/시간가중치
    edges.append((s,e,t))

#벨만-포드
distance[1] = 0 # 1번째 도시에서 출발

for i in range(N-1): # 경로 노드개수-1 최대
    for s,e,t in edges:
        if distance[s] != sys.maxsize and distance[e] > distance[s]+t: #접근불가 노드 판별해야 하므로 첫째조건
            distance[e] = distance[s]+t

#음수 사이클 확인!
mCycle = False

for s,e,t in edges:
        if distance[s] != sys.maxsize and distance[e] > distance[s]+t: #변동사항이 있다면
            mCycle = True

#결과
if not mCycle:
    for i in range(2,N+1):
        if distance[i] != sys.maxsize:
            print(distance[i])
        else:
            print(-1)
else: #음수 사이클임
    print(-1)

아 N-1 번마다 모든 노드값들 확인하는코드!!!

edges들 한번씩만 보는 줄 알고 한참 고민했네..ㅜ

---

✳️플래티넘 

1219번: 오민식의 고민

최단거리가 아닌 최댓값을 구하는 문제이므로 "반대로"생각해야 함!

'Gee' 를 알기 위해서는 음수 사이클 확인이 아닌 "양수 사이클" 확인 절차가 필요함

이라고 교재가 그랬지만

그냥 - 붙이고 로직 똑같이 하면 되는 거 아닌가

import sys
N,A,B,M = map(int,sys.stdin.readline().split()) #노드(도시)/시작도시/도착도시/에지(교통수단)
edges =[] # 에지리스트
distance = [-sys.maxsize] *(N+1) #거리 결과리스트


for _ in range(M):
    s,e,t = map(int,sys.stdin.readline().split()) #시작노드/끝노드/시간가중치
    edges.append([s,e,-t])
cityMoney = list(map(int,sys.stdin.readline().split()))#도시에서 얻을 수 있는 돈
for i in range(M):
    edges[i][2] += cityMoney[edges[i][1]] #해당 이동으로 얻을 수 있는 돈 최종

#벨만-포드 
distance[A] = cityMoney[A] # 시작도시에서 출발

for i in range(N-1): # 경로 노드개수-1 최대
    for s,e,t in edges:
        if distance[s] != -sys.maxsize and distance[e] < distance[s]+t: #접근불가 노드 판별해야 하므로 첫째조건
            distance[e] = distance[s]+t

#양수 사이클 확인!
mCycle = False

#양수 사이클이 도착 도시와 연결되어 있는지도 알아야 함!
# N==1 예외
if N==1:
    k = 1
else: 
    k= N-1
for i in range(k):
    if mCycle:
        break
    for s,e,t in edges:
            if distance[s] != -sys.maxsize and distance[e] < distance[s]+t: #변동사항이 있다면
                distance[e] = sys.maxsize
                if e == B: #도착노드에 도달한다면
                    mCycle = True
                    break

#결과
if not mCycle:
    if distance[B] == -sys.maxsize: #도달불가
        print("gg")
    else:
        print(distance[B])
else: #양수 사이클-돈무한
    print("Gee")

으학 죽을 뻔했다

게시판 반례들 고마워요!

사이클 찾는 부분에서 극단적으로 치닫는 숫자에서는 도착노드까지 그 i횟수로는 부족할 수 있기 때문에, 애초에 사이클인 부분이면 언젠가는 max까지 도달할 것이므로 바로 max처리해줘서 N-1정도로 충분하게 했다

또 N==1 일 떄 예외를 따로 처리해줬다.

오래..걸렸다

+ 최솟값 : -sys.maxsize