baepoce   4년 전

플로이드 와샬 알고리즘이 3중포문써서 한번에가는것보다 다른한곳을 거쳐가는경우를 비교하는것이던데 

예를들어서

1-2

20 비용

1-3 3-2

4    10  비용

1-3 3-4 4-2
4      2     1   비용

1-4   4-2

  11    2     비용 

만약 입력이 이렇게 주어진다면 1-2로갈때  1-3 3-4 4-2 이렇게가 최소비용인데 이럴경우는 입력으로 주어지지 않는건가요?
알고리즘에 대해 잘몰라서 질문합니다

sait2000   4년 전

플로이드를 쓰면 최소비용이 나옵니다. 플로이드를 맞게 구현했다면 7이 나와야합니다.

baepoce   4년 전

아 자세히보니까 이해가 되네요 감사합니다

댓글을 작성하려면 로그인해야 합니다.