모든 쌍에 대한 최단 경로를 나타낸 배열 D를 구하는 과정
등록일 / 수정일- 페이지 / 형식
- 자료평가
- 구매가격
- 2021.02.18 / 2021.02.18
- 4페이지 /
pptx (파워포인트 2007이상) - 평가한 분이 없습니다. (구매금액의 3%지급)
- 800원
최대 20페이지까지 미리보기 서비스를 제공합니다.
자료평가하면 구매금액의 3%지급!
1
2
3
4
추천 연관자료
- 하고 싶은 말
- 모든 쌍에 대한 최단 경로를 나타낸 배열 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
자료평가
-
아직 평가한 내용이 없습니다.
