'플로이드워셜' 태그의 글 목록

먼저 초기화에 대한 설명이다. 어떤 노드 i 에서 j 로 가는데, L0 이므로 , 아무 노드도 거치지 않고 가겠다 라는 뜻이다. 즉 i 와 j 의 직접연결 비용에 대한 값이다. 만약 i 와 j 가 연결되어 있지 않다면, 무한대를 반환한다. 그림으로 보이면 다음과 같다. 다음은 2번에 대한 설명이다. i 에서 j 로 갈 때, 1~n+1 번 노드를 거칠 수 있다. 그 때의 최소비용을 구하는 식이다. 최소비용 1 . i 에서 j 까지 가는데, 1~n번 노드를 거쳐서 갈 때의 최소비용 2. i 에서 n+1 번 노드를 반드시 들려서, j 로 갈 때의 최소비용 1과 2중에서 작은값이 최소비용이 된다. 그림으로 보면 다음과 같다. 초록색이 1번이고, 파란색으로 가는 3가지 방법이 2번이다. ..