플로이드 워셜 알고리즘이란
모든 최단경로를 구하는 알고리즘이다.
다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘(S.S.S.P - Single Source Shortest Path) 이었다면,
플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있다
한붓그리기인 오일러서킷 과는 다르다
오일러 서킷은 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 말한다. 반드시 시작점으로 돌아와야하며, 한 번 지나간 선으로는 지나가지 않고 모든 선을 이어 그림을 완성하는 것이다. 나중에 오일러 서킷을 알아보도록 하겠다.
플로이드 - 워셜 알고리즘은 O(N^3) 이기 때문에 N이 20 만 넘어가도 엄청나게 된다.
모든 노드 간의 최단거리를 구해야 하므로 2차원 인접행렬로 만든다.
그리고 자기자신은 0 으로 표현할 수 있다.
INF = int(1e9)
graph = [[INF] * (n + 1) for _ in range(n + 1)]
for a in range(1, n + 1):
for b in range(1, n + 1):
if a == b:
graph[a][b] = 0
이 문제로 예시를 들어보겠다.
만약 2에서 4 로 가는방법은
2 > 3 > 4 도 가능하고
2> 1 > 4 도 가능하고
2 > 1 > 4 > 5 등등 가능하다.
이것을 코드로 표현하면 이렇게 된다.
# 2. 플로이드 - 와샬 알고리즘
for k in range(1, n + 1): # 경유지
for a in range(1, n + 1): # 출발지
for b in range(1, n + 1): # 도착지
# a > b 랑 a > k > b중에 최솟값으로 바꿔줌
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])k가 1일때
1 을 경유하여
a에서 b 까지 가는경우
k가 2일때
2 를 경유하여 a 에서 b를 가는경우
이런식으로 하나하나 다 체크한다.
모든 노드들을 중간 노드로 선정하는 과정을 각 라운드마다 거친다.
만약 이렇게 바뀌었다고 생각해보고 저위에 코드를 봐보자.
만약 1 > 4 를 생각하면
1> 4 보다 1>2>3>4 가 더 최솟값이다.
근데 1>2>3>4 가 나오려면 1>2 ,2>3, 3>4 를 다 알아야한다.
그래서 경유지인 k를 사용하여 1부터 돌리면서
k가2 일때 1>2>3 를 알게되는데 즉 1> 3 가는 최선 방법이다.
그리고 k 가 3 이 되면
1> 경유지3 > 4 으로 진행이 된다.
그걸 코드로 옮겨와서 확인하면 아래와 같다.
k = 2 일때 graph[1][3] 을 알게된다. 1> 2> 3
k = 3 일때 graph[1][4] 을 알게된다. 1 >3>4
근데 k = 2일때 graph[1][3] 을 구해뒀다.
좀 말이 어려운데,, 따라가면서 하면 이해가 될 수 있다..
관련문제
(Python/🥇5)백준알고리즘 21278번: 호석이 두 마리 치킨
문제 바로가기 문제: 컴공 출신은 치킨집을 하게 되어있다. 현실을 부정하지 말고 받아들이면 마음이 편하다. 결국 호석이도 2050년에는 치킨집을 하고 있다. 치킨집 이름은 "호석이 두마리 치킨"
windy7271.tistory.com
(Python/🥇3)백준알고리즘 11404 플로이드
문제 바로가기 문제: n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모
windy7271.tistory.com
댓글