다익스트라 알고리즘 같은 경우에는 하나의 정점에서 출발해서 모든 정점으로의 최단거리를 구할 수 있는 반면에,
플로이드-와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단거리를 구할 수 있다.
이 알고리즘의 핵심은 거쳐가는 정점을 기준으로 최단거리를 구한다는 점이다.
다익스트라에 비해서 구현 난이도가 훨씬 쉽다! 와!! 삼중 반복문!!!
아래 코드는 파이썬으로 구현한 플로이드-와샬 알고리즘 예시이다.
백준 11404번 플로이드)
import sys
INF = sys.maxsize
input = sys.stdin.readline
n, m = int(input()), int(input())
dis = [[INF]*n for _ in range(n)]
for _ in range(m):
a, b, c = map(int, input().split())
if c < dis[a-1][b-1]:
dis[a-1][b-1] = c
for k in range(n):
for a in range(n):
for b in range(n):
if a != b:
dis[a][b] = min(dis[a][b], dis[a][k]+dis[k][b])
for i in range(n):
for j in range(n):
if dis[i][j] == INF:
dis[i][j] = 0
for t in dis:
print(*t)
백준 알고리즘 문제 풀이)
jinho-study.tistory.com/1017?category=911939
백준 알고리즘 11404번 플로이드(python)
기본적인 플로이드-와샬 문제이다. import sys INF = sys.maxsize input = sys.stdin.readline n, m = int(input()), int(input()) dis = [[INF]*n for _ in range(n)] for _ in range(m): a, b, c = map(int, inp..
jinho-study.tistory.com
백준 알고리즘 2458번 키 순서(python)
기본적인 플로이드-와샬 문제이다. PyPy3로 제출해야 통과된다. (특정 노드가 다른 노드를 가리키는 횟수 + 다른 노드가 특정 노드를 가리키는 횟수) == N-1이라면 그 특정 노드의 순서를 알 수 있다
jinho-study.tistory.com
백준 알고리즘 11403번 경로 찾기(python)
기본적인 플로이드-와샬 문제이다. graph[a][k] == 1 and graph[k][b] == 1 이면 a에서 b로 갈 수 있다라는 점이 핵심이다. N = int(input()) graph = [list(map(int, input().split())) for _ in range(N)] for..
jinho-study.tistory.com
https://jinho-study.tistory.com/1085
프로그래머스 Level 3 순위
순위를 정확하게 매길 수 있는 사람이 몇 명인지 찾는 문제이다. 플로이드 와샬 알고리즘을 모른다면 풀기 조금 힘들 것 같은 문제이다. 플로이드 와샬을 사용해서 최단경로가 아닌 승패를 확인
jinho-study.tistory.com
'Agorithm > 자료구조, 알고리즘 정리' 카테고리의 다른 글
| 다익스트라(Dijkstra) 알고리즘 (백준 문제 포함) (0) | 2021.03.22 |
|---|---|
| 우선순위 큐, 힙(Priority Queue, heap) (백준 문제 포함) (0) | 2021.03.22 |
| 퇴각검색(Backtracking) (백준 문제 포함) (0) | 2021.03.20 |
| 동적 계획법(Dynamic programming) (백준 문제 포함) (0) | 2021.03.17 |
| 너비 우선 탐색(breadth-first search, BFS) (백준 문제 포함) (0) | 2021.03.10 |
