검색어 입력폼

모든 쌍에 대한 최단 경로를 나타낸 배열 D를 구하는 과정

저작시기 2018.02 | 등록일 2020.02.17 | 최종수정일 2020.02.20 파워포인트파일 MS 파워포인트 (pptx) | 4페이지 | 가격 800원

소개글

"모든 쌍에 대한 최단 경로를 나타낸 배열 D를 구하는 과정"에 대한 내용입니다.

목차

없음

본문내용

아래 그림(1)은 모든 쌍 최단 경로에 대한 동적 계획 알고리즘 수행하는 과정중 제일 첫 번째 단계로 각 점에서 다른 점들까지의 최단 경로의 거리를 나타낸 것이다. 그림(2)는 k=3으로 해서 점 3을 경유 가능한 점으로 고려해서 모든 쌍에 대한 최단 경로를 나타낸 그림이다. 다음 단계로 점 4를 경유 가능한 점으로 고려해서 모든 쌍에 대한 최단 경로를 나타낸 배열 D를 구하는 과정을 자세히 쓰시오. (해당 주차 및 교시: 4강 1차시)
<그림1>

– D[2,3] = min{D[2,3], D[2,1]+D[1,3]} = min{1, ∞+2} = 1
– D[2,4] = min{D[2,4], D[2,1]+D[1,4]} = min{∞, ∞+5} = ∞
– D[2,5] = min{D[2,5], D[2,1]+D[1,5]} = min{4, ∞+∞} = 4
– D[3,2] = min{D[3,2], D[3,1]+D[1,2]} = min{3, 1+4} = 3
– D[3,4] = min{D[3,4], D[3,1]+D[1,4]} = min{1, 1+5} = 1

참고 자료

없음
다운로드 맨위로