공부 기록장

이 알고리즘은 Floyd-Warshall 알고리즘이라고 불리기도 하고, 줄여서 floyd 알고리즘이라고 불리기도 한다. 이 알고리즘도 다익스트라와 비슷하게, 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로를 찾는 것이다. 하지만 다익스트라와는 다르게 가중치가 음의 값을 가지고 있어도 되고, 모든 쌍의 최단경로를 구하는 알고리즘이기 때문에 계산이 끝난 후에는 내 마음대로 출발점과 끝나는 점을 잡아도 최소 거리를 알려준다. 이 알고리즘은 점화식을 통해 계산을 하는데, 간단하게 생각해야 이해하기 쉽다. 1) 출발지에서 경유지를 거쳐, 도착지 까지 간다. 2) 출발지에서 도착지로 바로 가는 경우와 출발지에서 경유지를 거쳐 도착지로 가는 경우 중 더 빠른 길을 담아둔다..

이 문제는 swea D6 레벨 문제이다. 이 문제는 플로이드-마샬, Floyd 알고리즘을 가지고 풀었다. 1) 모든 경유지에 대해서 2) 출발지부터 도착지까지 가는데, 경유지를 거쳐서 가는 것과 바로 가는 것 중에 작은 값을 저장해준다. 라는 어찌보면 간단한 완전탐색 알고리즘이다. 근데 만약 이 알고리즘을 배우지 않았다면 좀 많이 헤맸을 것 같다. import java.util.Scanner; public class 사람네트워크2 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int tc=1; tc