Floyd Warshall Algorithm

[백준(BOJ)] #1507- 궁금한 민호 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B www.acmicpc.net 문제 풀이 입력으로 모든 도시로 가는 최소 이동 시간이 주어져 이를 역으로 풀어야 합니다. 즉, 플로이드 워셜 알고리즘을 역으로 적용하는 문제입니다. 2022.08.01 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 플로이드 워셜(Floyd Warshall) 알고리즘 [파이썬으로 배우는 알고리즘] 플로이드 워셜(Floyd Warshall) 알고리즘 플로이드 ..

[파이썬으로 배우는 알고리즘] 플로이드 워셜(Floyd Warshall) 알고리즘

플로이드 워셜(Floyd Warshall) 알고리즘이란? 플로이드 워셜(Floyd Warshall) 알고리즘은 최단 경로 알고리즘이지만 그래프에서 특정한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 다익스트라 알고리즘과 달리 모든 정점으로부터 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 플로이드 워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 동적 계획법을 활용한 알고리즘입니다. 2022.07.31 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 다익스트라(Dijkstra) 알고리즘 [파이썬으로 배우는 알고리즘] 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘이란? 다익스트라(Dijkstra) 알고리즘은 최단 경로 알고리즘으로 그래프에서 특정한 노드에서..