플로이드 알고리즘
모든 정점 쌍 사이의 최단거리를 구해주는 알고리즘
(방향 / 무방향 상관없음)
1번 노드를 반드시 거치는 것과 현재 테이블의 값과 비교 후 비용의 총합이 더 작은 것을 갱신
2. 1번 을 노드의 수만큼 반복
복잡도 : O(V**3)
정점 450개면 약 1억 연산이지만 플로이드는 단순 사칙연산이라 정점 1000개 근사치 가능
-구현 : 자주쓰던 인접리스트가 아니라, 인접행렬 그자체를 쓰는 테이블임
start==end 부분은 나중에 한번에 0처리 하기 위해 continue로 넘어가도록 한다.
import sys
n = int(input())
e = int(input())
matt = [[10001000]*(n+1) for __ in range(n+1)]
for _ in range(e):
s,t,cost = map(int, sys.stdin.readline().strip().split())
if matt[s][t] > cost:
matt[s][t] = cost
#matt[t][s] = cost 무방향
for node in range(1, n+1):
for st in range(1, n+1):
for end in range(1, n+1):
if st==end:
continue #같은 곳일때는 연산하지 않는게 낫다. 나중에 10001000을 한번에 0 만들거임
if (matt[st][node] + matt[node][end]) < matt[st][end]:
matt[st][end] = (matt[st][node] + matt[node][end])
#matt[end][st] = (matt[st][node] + matt[node][end]) 무방향
for ii in range(1, n+1):
for jj in range(1, n+1):
if matt[ii][jj] == 10001000:
matt[ii][jj] = 0 #문제의 조건에 따라 처리한다.
print(matt[ii][jj], end = ' ')
print("", end = '\n') 무방향일때 하나만 넣을 수 있고, 문제의 조건에 따라 y,x 초기화 잘해야 한다.
최대값은 간선의 최댓값이 아닌, n*간선의 최대값을 주는 것에 주의한다.
경로를 추적할 때
nxt 배열을 만든다
nxt : table배열이 갱신될 때, 반드시 지나가는 [node]를 담는 배열
참고자료 및 출처 : 바킹독 알고리즘 강의(유튜브) (🙏🙏🙏) > 링크
-
nxt 초기화 : 직접적으로 이어진 것만 배열에 담는다.
-
최단거리 table이 갱신될때 [node]를 반드시 거쳐가므로
해당 하는 위치인 nxt[start][end] 에다가 nxt[start][node]의 값을 담는다. (노드를 거쳐서 end로 가야한다는 의미)
node = 1일때
node = 2일때 -
계속 덮어쓰면서 최종 nxt를 만든다
테이블이 다 완성되었으므로 경로를 추적한다.
경로 추적 방법
nxt[tempstart][end]의 값을 봐서 그 값이 end가 될때까지 end의 값을 tempstart로 초기화하고
만나는 값마다가 지나는 노드가 된다.
-구현
for ss in range(1,n+1):
for endd in range(1, n+1):
if nxt[ss][endd]==0:# 경로가 없는 경우
print(0)
continue
q = deque()
tst = ss
q.appendleft(ss)
while(1):
q.appendleft(nxt[tst][endd])
if nxt[tst][endd]==endd: #or 추가. 아무 연결이 없는 경우 생각필요함
break
tst=nxt[tst][endd]경로 추적 전체 코드 (11780)
import sys
from collections import deque
n = int(input())
m = int(input())
table = [[10000010]*(n+1) for __ in range(n+1)]
nxt = [[0]*(n+1) for __ in range(n+1)] #nxt도 초기화 고민필요
for _ in range(m):
s, e, cost = map(int, sys.stdin.readline().strip().split())
if table[s][e] > cost:
table[s][e] = cost
#table[e][s] = cost 무방향
nxt[s][e] = e
#nxt[e][s] = s 무방향 nxt는 무방향이어도 비대칭성이다
for node in range(1, n+1):
for st in range(1, n+1):
for end in range(1,n+1):
if st==end:
continue
if (table[st][node]+table[node][end]) < table[st][end]:
table[st][end] = (table[st][node]+table[node][end])
nxt[st][end] = nxt[st][node]
#mmap[end][st] = (mmap[st][node]+mmap[node][end]) 무방향 : 값은 동일하니 유지
#nxt[end][st] = nxt[end][node] 무방향:의미적으로 이게 맞다
for tt in range(1,n+1):
for ff in range(1,n+1):
if table[tt][ff] == 10000010:
table[tt][ff] = 0
nxt[tt][ff] = 0
for t1 in range(1, n+1):
for t2 in range(1, n+1):
print(table[t1][t2], end = ' ')
print("")
for ss in range(1,n+1):
for endd in range(1, n+1):
if nxt[ss][endd]==0:#ss == endd랑 헷갈렸음.
print(0)
continue
q = deque()
tst = ss
q.appendleft(ss)
while(1):
q.appendleft(nxt[tst][endd])
if nxt[tst][endd]==endd:
break
tst=nxt[tst][endd]
print(len(q),end = ' ')
while(q):
print(q.pop(),end = ' ')
print("",end = '\n')주석 부분 주의:
(주석)ss == endd랑 헷갈렸음. 부분을 ss==end로 해버리면 시작점 끝점이 같은경우만 따지지만
사실 경로가 존재하지 않는 경우를 따지지 못해 아래의 while문으로 들어가게 된다.
아래 while은 nxt[tst][endd]==endd를 만나기전까지 루프를 돌지만 경로가 없으면 무한루프이다.
