[최단경로] 플로이드 워셜 알고리즘 정리 외 2문제

출처 - 이것이 코딩테스트다 with Python

플로이드 워셜 알고리즘

1. 다익스트라 알고리즘과의 비교

다익스트라 알고리즘 - 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘

플로이드 워셜 알고리즘 - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

---

• 다익스트라 알고리즘
  매 단계 마다 최단 거리 테이블에서 최솟값을 가지는 노드를 하나씩 선택한다.
  그리고 해당 노드를 거쳐 가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작한다.

• 플로이드 워셜 알고리즘
  플로이드 워셜 알고리즘 또한 단계 마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다.

하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다.

---

2. 플로이드 워셜 알고리즘의 특징

• 2차원 리스트에 '최단 거리' 정보를 저장한다는 특징을 가지고 있다.
  - 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다.
  - 2차원 리스트를 처리해야 하므로 N번의 단계에서 O(N^2)의 시간이 소요가 된다. (총 O(N^3)의 시간이 소요된다.)

• 다이나믹 프로그래밍이라는 특징이 있다.
  - 노드의 개수가 n개라고 할 때, n번의 단계에 대해 "점화식에 맞게" 2차원 리스트를 갱신하기 때문이다.

  구체적인 점화식 - Dab = min(Dab, Dak+Dkb)
  (a->b로 바로 가는 비용과, a->k->b로 가는 비용을 비교함)

---

3. 플로이드 워셜 알고리즘 구현

책에 나온 과정을 그대로 코드로 작성하면 아래와 같다.

INF = int(1e9) #무한 값 설정

n = int(input()) #노드의 수
m = int(input()) #간선의 수 

graph = [[INF]*(n+1) for i in range(n+1)] #2차원 리스트를 만들고 모든 값을 INF로 초기화

#자기 자신으로 가는 비용은 0으로 초기화
for i in range(1,n+1):
    for j in range(1,n+1):
        if i==j:
            graph[i][j] = 0

#간선과 비용 입력받기
for i in range(m):
    s,e,dist = map(int,input().split())
    graph[s][e] = dist #단방향 그래프

#플로이드 워셜 실행
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("INF", end=" ")
        else:
            print(graph[i][j], end=" ")
    print()

플로이드 워셜 알고리즘을 수행하는 코드는

#플로이드 워셜 실행
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][i])

이 부분이다.

---

이 때, for 문의 순서를 주의해야 한다.

• 첫번째 k : 거쳐가는 노드
• 중간 i : 시작 노드
• 마지막 j : 도착 노드

---

틀린 경우
첫번째 k: 시작 노드
중간 i: 도착 노드
마지막 j:거쳐가는 노드 라고 한다면

예를 들어 graph[1][2]의 최소비용을 얻고 싶다면

for j in range(1,n+1):
	graph[1][2] = min(graph[1][2],graph[1][j]+graph[j][2])

로 수행이 된다.

이렇게 되면 graph[1][2]의 값은 매 단계 마다 업데이트 되는 것이 아니라 한 번 수행하고 끝이 나게 된다.

=> 거쳐가는 노드를 기준으로 삼아서 매 단계마다 업데이트 하는 방식으로 해야 한다.

---

문제풀이 2문제

미래 도시

1. 플로이드 워셜로 푼 방식

INF = int(1e9)
#노드와 간선 입력
n,m = map(int,input().split())

graph =[[INF]*(n+1) for i in range(n+1)] #무한대로 초기화한 그래프 생성

#자기자신은 0으로 맞춤
for i in range(1,n+1):
    for j in range(1,n+1):
        if i==j:
            graph[i][j]=0

#m개의 간선 입력받기 
for i in range(m):
    s,e = map(int,input().split())
    graph[s][e]=1 #양방향 그래프+거리는 무조건 1
    graph[e][s]=1

#마지막 줄에 x,k입력받기
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])

if graph[1][k]==INF or graph[k][x]==INF:
    print(-1)
else:
    print(graph[1][k]+graph[k][x])

플로이드 워셜 알고리즘을 통해서 모든 시작 노드에서 모든 도착 노드까지의 거리를 구하고 (1->k 비용)+(k->x 비용)을 구해줬다.

2. 다익스트라 알고리즘

import heapq

INF = int(1e9)
#노드와 간선 입력
n,m = map(int,input().split()) #노드와 간선 입력받기

graph = [[] for i in range(n+1)] #빈 인접리스트 생성
distance = [INF]*(n+1) #1차원의 거리 리스트 생성

#간선 입력 받기
for i in range(m):
    s,e = map(int,input().split())
    graph[s].append([e,1])
    graph[e].append([s,1]) #양방향 그래프 (노드, 거리)

x,k = map(int,input().split()) #x,k입력받기

def dijkstra(start):
    q = []
    distance[start] = 0 #출발노드는 거리 0
    heapq.heappush(q,(0,start))
    
    while q:
        dist,node = heapq.heappop(q)
        if distance[node] < dist: #이미 방문했었던 노드라면 무시
            continue
        for i in graph[node]:
            cost = dist+i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))

#1에서 k까지 구하기
dijkstra(1)
answer = distance[k]

#k에서 x까지 구하기
dijkstra(k)
answer+=distance[x]

if answer>=INF:
    print("-1")
else:
    print(answer)

먼저 다익스트라 알고리즘을 구현하고, 2번의 함수 호출을 통해서 결과 값을 얻었다.

전보

import heapq

#무한대 값 설정하기
INF = int(1e9)

#노드, 간선, 출발지
n,m,c = map(int, input().split())

graph=[[] for i in range(n+1)]
distance=[INF]*(n+1)

#간선, 비용 입력받기
for i in range(m):
    x,y,z = map(int,input().split())
    graph[x].append([y,z]) #단방향 그래프
    
def dijkstra(start):
    q=[]
    distance[start] = 0
    heapq.heappush(q,(0,start)) #시작노드 push
    
    while q:
        dist, node = heapq.heappop(q)
    
        if distance[node] <dist: #이미 방문한 노드
            continue
        
        for i in graph[node]:
            cost = distance[node]+i[1] #출발지부터 node+ node부터 i[0]까지의 거리
            
            if cost<distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))
                
count=0
total = 0
dijkstra(c)

for i in range(1,n+1):
    if distance[i]!=INF:
        count+=1
        total = max(total, distance[i])
        
#count에서 자기 자신은 뺀다. 
print(count-1, total)

시작노드가 주어졌기 때문에 다익스트라 알고리즘으로 구현하였다.

출발노드에서 전보를 돌릴 수 있는 노드의 개수를 구하라고 했으므로, distance리스트에서 값이 INF가 아니라면 count+=1을 해주었다.