[python] 플로이드 워셜(Floyd-warshall)알고리즘이란?
[python] 플로이드 워셜(Floyd-warshall)알고리즘이란? — #플로이드워셜 #floydwarshall #파이썬알고리즘 #개발자의도구들 AI스쿨 msa기반 java 백엔드 코스 중에 ...
#플로이드워셜 #floydwarshall #파이썬알고리즘 #개발자의도구들
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다
\* 하루 1코테 도전중에 있습니다. 어떤건지 궁굼하신 분들은 여기를 눌려주세요.
하루 1코테
현재 계속해서 하루 1코테 챌린지를 하고 있습니다. 학습시간 기준이며 하루 학습량은 대략 1~1.5시간 정도가 되겠습니다.
원래 노션에 개인적으로 노트정리를 하였지만, 혼자서 정리하는 것 보단, 함께 공유하는 것이 낫고 복습글을 작성하는게 공부효율에 좋을 것 같아 글을 계속 남겨볼 생각입니다.
취업은 아마 내년 이맘때쯤 준비할 예정인데, 가능하다면 최상위 코딩테스트 문제까지 푸는 실력까지 갖추고 싶습니다. 부족한게 많지만 꾸준히 해나가고 싶습니다.
플로이드 워셜(floyd-warshall) 알고리즘이란?
기본 이론
Dijsktra 알고리즘과 결이 비슷한 floyd-warshall알고리즘은 모든 정점에서 이웃하는 정점에 대한 최단거리를 구하는 방법입니다.
Dijkstra는 시작점이 주어지고 그 점에서 각 정점에 대한 최단거리를 구했지만, floyd-warshall은 모든 점이 시작점이되고 각 시작점과 이어진 모든 정점의 최단거리를 구하는 방법입니다.
똑같이 최단거리를 구하는 알고리즘이나, 하나의 정점에서 알고싶으면 Dijstra, 모든 정점에서 알고싶으면 floyd-warshall을 사용합니다.
원리
원리는 매우 간단합니다. 단순 반복에 가깝습니다.
위와 같은 그래프를 먼저 고려해봅시다. 현재 위치정보는 아래와 같습니다.
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | INF | 1 | INF | 3 |
| 2 | INF | 0 | 6 | INF | 2 |
| 3 | 1 | 6 | 0 | 1 | INF |
| 4 | INF | INF | 1 | 0 | 4 |
| 5 | 3 | 2 | INF | 4 | 0 |
floy-warshall은 모든 정점에 대하여 중간노드를 한번씩 설정하여 최단거리를 찾아갑니다. 현재 그래프의 정점이 5개이므로 총 5번의 중간노드가 1~5까지 순서대로 설정됩니다.
1라운드
중간노드 = 1 (주황색)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | INF | 1 | INF | 3 |
| 2 | INF | 0 | 6 | INF | 2 |
| 3 | 1 | 6 | 0 | 1 | ~~INF~~ 4(3 -> 1 -> 5) |
| 4 | INF | INF | 1 | 0 | 4 |
| 5 | 3 | 2 | ~~INF~~ 4(5->1->3) | 4 | 0 |
각 지점에서 새로운 최단거리를 계산합니다. 1번 노드는 중간노드가 되며, 각 노드에서 거리를 계산할때 이 중간노드의 값을 참조합니다.
2라운드
중간노드 = 2 (주황색)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | INF | 1 | INF | 3 |
| 2 | INF | 0 | 6 | INF | 2 |
| 3 | 1 | 6 | 0 | 1 | 4 |
| 4 | INF | INF | 1 | 0 | 4 |
| 5 | 3 | 2 | 4 | 4 | 0 |
이번에는 각 노드가 중간노드 2번을 참조합니다. 3번 노드의 경우 3 -> 2 -> 5의 값이 8인데 기존의 값 4보다 크기때문에 업데이트 되지 않습니다.
3라운드
중간노드 = 3 (주황색)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | ~~INF~~ 7 | 1 | ~~INF~~ 2 | 3 |
| 2 | ~~INF~~ 7 | 0 | 6 | ~~INF~~ 7 | 2 |
| 3 | 1 | 6 | 0 | 1 | 4 |
| 4 | ~~INF~~ 2 | ~~INF~~ 7 | 1 | 0 | 4 |
| 5 | 3 | 2 | 4 | 4 | 0 |
4라운드
중간노드 = 4 (주황색)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | 7 | 1 | 2 | 3 |
| 2 | 7 | 0 | 6 | 7 | 2 |
| 3 | 1 | 6 | 0 | 1 | 4 |
| 4 | 2 | 7 | 1 | 0 | 4 |
| 5 | 3 | 2 | 4 | 4 | 0 |
5라운드
중간노드 = 5 (주황색)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | ~~7~~ 5 | 1 | 2 | 3 |
| 2 | ~~7 ~~5 | 0 | 6 | ~~7~~ 6 | 2 |
| 3 | 1 | 6 | 0 | 1 | 4 |
| 4 | 2 | ~~7~~ 6 | 1 | 0 | 4 |
| 5 | 3 | 2 | 4 | 4 | 0 |
5라운드의 마지막 값이 최종적으로 floyd-warshall의 결과가 됩니다.
구현(초기)
03.18
\*경고: 절대 해당 코드를 그대로 사용하지 마시오. 작동이 제대로 안될 것이오.
현재 python을 활용하여 floyd-warshall을 구현하고 있습니다. 처음 구현해보는 것이라 꽤나 시간이 걸릴 것 같지만, 진행상황을 점진적으로 공유해보고자 합니다.
| 구현에 앞서서 고려해야할 점은 다음과 같습니다. 1. 라운드를 고려할 것 2. 각 라운드의 중점 노드 경로를 계산에 더할 것 3. 각 라운드마다 경로 map의 값을 업데이트 할 것 |
|---|
distance\_map으로 사용될 형식
| # graph {# {1: {3: 1, 5: 3}}# {2: {3: 6, 5: 2}}# {3: {1: 1, 2: 6, 4: 1}}# {4: {3: 1, 5: 4}}# {5: {1: 3. 4: 4}}# }# vertext in graph => 1, 2, 3, 4, 5# map = {1: {vertxet not in graph\[vertxet\] = float("INF") 자기 자신 0으로 초기화 } }# {1: {1: 0, 2: INF, 3: 1, 4: INF, 5: 3}}# {2: {1: INF, 2: 0, 3: 6, 4: INF, 5: 2}}# {3: {1: 1, 2: 6, 3:0, 4: 1, 5: INF}}# {4: {1: INF, 2: INF, 3: 1, 4:0, 5: 4}}# {5: {1: 3. 2: INF, 3: INF, 4: 4, 5: 0}}## |
|---|
딕셔너리를 사용하여 graph를 입력 받고 모든의 정점에 대해 각 정점의 값을 셋팅할 생각입니다.
| import sys, heapq# 무 방향 가중치 그래프class Graph: def \_\_init\_\_(self): self.graph = {} self.node = \[\] def add\_node(self, node): self.node.append(node) def add\_edge(self, u, v, w): if u not in self.graph: self.graph\[u\] = {} if v not in self.graph: self.graph\[v\] = {} self.graph\[u\]\[v\] = w self.graph\[v\]\[u\] = wdef floyd\_warshall(graph): distance\_map = {} for vertext in graph.graph: node\_map = graph.graph\[vertext\] node\_map\[vertext\] = 0 for node in graph.node: if node not in node\_map: node\_map\[node\] = float("INF") distance\_map\[vertext\] = node\_map return distance\_mapgraph = Graph()n = int(sys.stdin.readline().rstrip())m = int(sys.stdin.readline().rstrip())for i in range(1, n + 1): graph.add\_node(i)for \_ in range(m): a, b, c = map(int, sys.stdin.readline().rstrip().split()) graph.add\_edge(a, b, c)print(graph.graph)print(floyd\_warshall(graph)) |
|---|
~~ 현재 초기 distance\_map을 구현하는데 까지 완료하였습니다. 나머지는 점차적으로 업데이트 해나가겠습니다. (24.03.18)~~
~~~~
위 코드는 올바르지 않게 작동합니다. 왜인지 스스로 생각을 한번 해보시고 다 하신분은 수정본을 확인해주세요.
구현 초기(탐색)
\*경고: 절대 코드를 그대로 사용하지 마시오 작동이 안됩니다.
기존의 동작원리를 잘 보아하니, 특정 공식이 보였습니다. 현재 map에는 이런 형태의 데이터가 저장되어 있습니다.(저는 딕셔너리를 사용하였습니다)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | INF | 1 | INF | 3 |
| 2 | INF | 0 | 6 | INF | 2 |
| 3 | 1 | 6 | 0 | 1 | INF |
| 4 | INF | INF | 1 | 0 | 4 |
| 5 | 3 | 2 | INF | 4 | 0 |
1번부터 5번까지를 각 중간노드로 두어 최단 경로를 결정합니다. 이미 함수내에는 모든 경로에 대한 정보가 들어 있습니다.
어차피 최단거리에 대한 정보를 미리 받아 놓고 하나씩 전부 돌려보는 알고리즘 이기 때문에 Dikstra처럼 heapq를 사용하지 않아도 구현할 수 있었습니다.
원리를 공식화하자면, 출발 노드(S), 중간노드(C), 목적노드(G)가 있는 상황을 고려해봅시다.
현재 S에서 G까지의 거리(기존 자료에 적혀있는 값)과 S에서 C까지 거리 + C에서 G까지 거리(플로이드 워셜 탐색 거리)를 비교하여 후자가 더 작은 경우에 업데이트틑 계속 해나가면 됩니다.
| for central\_node in range(1, len(graph.node) + 1): print("central node: ", central\_node) central\_node\_map = distance\_map\[central\_node\] print("central node map : ", central\_node\_map) for each\_node in graph.node: dist\_map = distance\_map\[each\_node\] print("dist\_map: ", dist\_map) for neighbor in dist\_map: print("neighbor, weigh: ", neighbor, "via central cost: ", dist\_map\[central\_node\] + central\_node\_map\[neighbor\]) if dist\_map\[neighbor\] > dist\_map\[central\_node\] + central\_node\_map\[neighbor\]: print("new distance set/ original: ", distance\_map\[neighbor\], "new dist: ", dist\_map\[central\_node\] + central\_node\_map\[neighbor\]) dist\_map\[neighbor\] = dist\_map\[central\_node\] + central\_node\_map\[neighbor\] return distance\_map |
|---|
코드는 이렇게 구현할 수 있겠습니다.
일단 이 코드를 사용하여 문제를 풀어보고 차츰 차츰 개선해 나가 보겠습니다.(24.03.19)