프로그래밍

3206,

154/161

ksbgenius

[자료구조]그래프 임계경로에 관련된 개념적 질문

http://www.hackerschool.org/HS_Boards/zboard.php?id=QNA_programming&no=3043 [복사]

제가 지금 자료구조 그래프에서 임계경로와 AOE네트워크 부분을 공부하고 있습니다.
그런데 한가지 헷갈리는게 있어서 질문 드립니다.
임계경로에
earliest time과 latest time 이 있는데
earliest time은 공정이 완료되는 시간이라서 알고 있는데
latest time은 책에 작업이 가장 늦게 시작될 수 있는 시간이라고 말하는데, 도통 헷갈려서 이해가 잘 안갑니다.
예를 들어서

정점 v1에서 v2를 가는데 작업 a1 = 6, v2에서 v5로 가는데 작업 a4 = 1,
v5에서 v7로 가는데 작업 a7 = 9,  v7에서 v9로 가는데 작업 a10 = 2
정점 v1에서 v3를 가는데 작업 a2 = 4, v3에서 v5로 가는데 작업 a5= 1,
v5에서 v8로 가는데 작업 a8 = 7, v8에서 v9로 가는데 작업 a11 = 4
정점 v1에서 v4를 가는데 작업 a3 = 5, v4에서 v6로 가는데 작업 a6 = 2,
v6에서 v8로 가는데  작업 a9 = 4
이렇게 AOE 네트워크가 있습니다.
그림으로 파일 첨부하고 싶은데....그림 첨부 하는게 없네요;;;;;

이 상태에서 제가 공부하고 있는 책에서는
작업     earliesttime      latesttime
a1            0                     0
a2            0                     2
a3            0                     3
a4            6                     6
a5            4                     6
a6            5                     8
a7            7                     7
a8            7                     7
a9            7                     10
a10         16                    16
a11         14                  14

이런 식으로 나와 있습니다.
earliesttime 은 알겠는데, latesttime이 많이 헷갈립니다.

Hit : 6235 Date : 2011/06/08 11:19