CPM 알고리즘을 설계하는 방법은 무엇입니까?

Question

리스트 데이터 구조로 그래프를 표현하는 방법 저는 세 개의 클래스 (Graph, Node, Edge)를 가지며 그래프에서 중요한 경로를 찾고 싶습니다.

• ES 계산하는 방법 : 가장 빠른 시작
• EC : 이른 전체
• LS : 최신 시작
• LC : 최신 전체

감사

Answer 1

그래프를 저장하기위한 또 다른 대안은 부스트 ​​그래프 라이브러리 (BGL)이다. 위키 백과에서 볼 수 있듯이 critical path은 두 꼭지점 간의 가장 긴 경로입니다. 또한 그것은 longest path을 찾는 것 같아 것은 NP 일반적인 경우에 대한하지만, 귀하의 경우 생각보다 효율적인 알고리즘이 존재 방향성 비순환 그래프 (DAG)을위한 완벽한입니다.

가장 긴 경로 알고리즘은 BGL에서가 아니라 위키 피 디아에 DAG 알고리즘은 구현하기가 합리적으로 쉽게 보인다.

Answer 2

을 우수 quickgraph 라이브러리에는 그래프를 설명하는 클래스가 있으며 shortest path을 비롯한 많은 수의 그래프 알고리즘이 있습니다. 너는 그런 것을 할 수 있을지도 모른다.

그래도 실제로는 표준 그래프 알고리즘보다 복잡합니다. Microsoft Project의 핵심을 간단한 알고리즘으로 사용할 수 있기를 원하는 것처럼 보입니다. 불행하게도 그렇지 않습니다. 프로젝트 복사본을 구입하고 COM API를 사용하여 계획을 수립하는 것이 좋습니다. 이는 환경에 따라 쉬운 방법 일 수 있습니다. 그래도 네가 너보다 먼저 일하게 될 것 같아.