컴퓨터 네트워크 #17

벨만-포드, 플로이드 워셜

---

먼저 초기화에 대한 설명이다.

어떤 노드 i 에서 j 로 가는데, L0 이므로 아무 노드도 거치지 않고 가겠다 라는 뜻이다.

즉 i와j 의 직접연결 비용에 대한 값이다. 만약 i와j 가 연결되어 있지 않다면 무한대를 반환한다.

그림으로 보이면 다음과 같다.

다음은 2번에 대한 설명이다.

i에서 j로 갈 때, 1 ~ n+1번 노드를 거칠 수 있다. 그 때의 최소비용을 구하는 식이다.

최소비용

• i에서 j까지 가는데, 1 ~ n번 노드를 거쳐서 갈 때의 최소비용
• i에서 n+1 번 노드를 반드시 들려서, j로 갈 때의 최소비용

1과 2중에서 작은값이 최소비용이 된다. 그림으로 보면 다음과 같다.

초록색이 1번이고, 파란색으로 가는 3가지 방법이 2번이다.

1 ~ n번 노드만 거쳐서 가는 최소비용이 원래의 최소비용이라고 생각하고, 여기에 n+1번 노드가 새로 생겼다고 보면 편하다.

이 n+1번 노드까지 고려한 최소비용은, 우리가 원래 알고 있던 최소비용(초록색)과, 새로 생긴 n+1번 노드를 거쳐 가면서 생기는 최소비용(파란색) 을 서로 비교해 작은 값을 선택하면 된다.

해설에 대한 영어 원문