데이터 구조 DAG 다 원 최 단 (장) 로 총화

목차

서문

DAG 최 단 길

설명

실현

DAG 최 장 로

설명

실현

DAG 의 모든 정점 대 간 최 단 로

설명

실현

머리말
먼저 DAG 가 무엇 인지 알 아야 한다. 고리 가 없 는 그림 이 있 으 면 토폴로지 정렬, 관건 적 인 경 로 를 구 할 수 있 고 공사 계획 에 큰 도움 이 된다.만약 에 어떤 문제 가 DAG 를 전제 로 하 는 것 을 발견 하면 DAG 의 무 권 성에 따라 가장 좋 은 서브 구 조 를 가지 고 있다 는 것 을 증명 할 수 있 고 \ (O (n + e) \) 의 복잡 도 에서 DAG 의 다 원 화 된 최 단 (최 장) 길 을 구 할 수 있다.그래서 정점 간 에 최 단 로 를 계산 할 때 우 리 는 일반 그림 의 Floyd 알고리즘 을 사용 할 수 있 습 니 다. 그 원 리 는 패 킷 을 전달 하 는 원 리 를 이용 하여 매번 \ (E ^ k = E ^ {k + 1} \), 경로 길이 + 1 에 해당 합 니 다. 동적 계획 을 바탕 으로 합 니 다. \ (dp [i] [j] = max (dp [i] [k] + dp [k] [j], dp [i] [j] \), 복잡 도 \ (O (n ^ 3) \).DAG 의 성질 을 이용 하여 우 리 는 \ (O (ne) \) 에서 완성 할 수 있 고 원리 도 동적 계획 에 기초 한 것 이다.
DAG 최 단 길
묘사 하 다.

먼저 저 는 그림 에 토폴로지 순 서 를 한 번 할 수 있 습 니 다. 이렇게 하 는 이 유 는 한 점 의 최 단 로 를 업데이트 할 때마다 그 점 에 전달 할 수 있 는 점 이 모두 계산 되 었 기 때 문 입 니 다. 토폴로지 순 서 는 바로 이 일 을 하 는 것 입 니 다. 그 후에 효과 가 없 기 때 문 입 니 다. 모든 점 의 최 적 화 된 결정 은 그 전에 어느 쪽 이 전 달 된 것 과 관계 가 없 기 때 문 입 니 다.

\ (O (n + e) \) 의 복잡 도 를 보장 하 는 전 제 는 인접 표 로 그림 을 저장 하 는 것 이다.

현재 지점 에 도착 하 는 가장 짧 은 경 로 를 pre 로 표시 하 는 전구 노드

다른 정점 에서 v 점 까지 의 최 단 경로 길 이 를 dist 로 표시 합 니 다

ts 로 토폴로지 정렬 표시

우선 path 는 0, c 는 INF, c [원점] = 0

으로 초기 화
문 제 를 말 하면 여기 dp 상태 dist 는 두 가지 이해 방식 이 있 습 니 다.

앞의 점 이 현재 의 최 단 로 (i 시 로 출발 하 는 최 단 로) (고정 종점)

각 노드 가 전달 하 는 최 단 로 (i 시 로 끝 나 는 최 단 로) (고정 기점)

분명 한 것 은 상태 2 의 표현 법 은 재 귀 하 는 과정 이다. 최적화 수단 은 바로 기억 화 이다. 그러나 일부 문제 (예 를 들 어 인접 표) 와 유사 하고 쉽게 얻 을 수 있 는 변 권 이지 만 쉽게 얻 지 못 하 는 변 권 (반 매 거 에 해당) 을 가 질 때 우 리 는 건축 그림 의 데이터 구조 (예 를 들 어 인접 행렬), 역방향 건축 변 등 을 바 꾸 는 동시에 '솔 표 법' 도 사용 할 수 있다.: 한 상태 에 이 를 때마다 인접 한 변 (다음 상태) 을 모두 전달 하 는 것 이다. 이런 방법 을 구별 하 는 일반적인 방법 은 표 작성 법 이다.그러나 상태 2 가 일부 사전 순 서 를 구 하 는 문제 에 대해 이 방법 은 구하 기 어렵다. 이때 상태 1 의 디자인 방식 을 사용 해 야 한다.
이루어지다

void shortTest() {
    Topsort(edge, ts); //        ts 
    for (int i = 0; i < ts.size(); i++) { //                     
        int cur = ts[i]; //    
        for (int j = 0; j < edge[cur].size(); j++) {
            edge& v = edge[cur][j]; //        
            if (c[v.to] > c[cur] + v.w) { //      
                c[v.to] = c[cur] + v.w; //update
                pre[v.to] = cur; //      
            }
        }
    }
}

DAG 최 장 로
묘사 하 다.
DAG 최 단 로 와 유사 합 니 다. 업데이트 할 때마다 조건 을 바 꾸 면 됩 니 다.
이루어지다

void shortTest() {
    Topsort(edge, ts); //        ts 
    for (int i = 0; i < ts.size(); i++) { //                     
        int cur = ts[i]; //    
        for (int j = 0; j < edge[cur].size(); j++) {
            edge& v = edge[cur][j]; //        
            if (c[v.to] < c[cur] + v.w) { //        ：         
                c[v.to] = c[cur] + v.w; //update
                pre[v.to] = cur; //      
            }
        }
    }
}

DAG 의 모든 정점 대 사이 의 최 단 로
묘사 하 다.
마찬가지 로 DAG 의 그림 에서 가장 좋 은 서브 구조 에 따라 동적 계획 을 하 는데 핵심 적 인 사 고 는 \ (dfs \) 를 이용 하여 모든 것 을 구 하 는 것 이다.
인접 점 의 최 단 로 는 결 과 를 행렬 에 저장 합 니 다.
계산 이 끝나 고 가장 좋 으 며 많은 최 단 로 알고리즘 에 따라 느슨 해 질 수 있 으 며 느슨 해 지 는 것 은 삼각형 을 이용 하 는 것 이다.
등식 은 바로 bellman 방정식 을 나머지 이웃 접점 으로 업데이트 하 는 가장 짧 은 길 입 니 다. 물론 연결 되 지 않 으 면 안 됩 니 다.
업데이트 가 가능 합 니 다.구체 적 인 과정 은 다음 과 같다.

모든 점, 즉 dp 를 INF 로 미리 처리 합 니 다. 즉, 초기 상황 에서 모든 점 이 연결 되 지 않 습 니 다. 물론 자신 도 연결 되 지 않 습 니 다. 이렇게 하 는 역할 은 한 점 이 계산 되 었 는 지 여 부 를 편리 하 게 판단 하기 위해 서 입 니 다.물론 하나의 vis 로 모든 점 이 검색 되 었 는 지 여 부 를 표시 할 수도 있 습 니 다. 다만 이러한 공간 이 많 을 뿐 읽 을 수 있 습 니 다. 많은 기억 화 검색 은 이 기술 을 사 용 했 습 니 다.

검색 할 때마다 \ (dp [cur] [cur] \) 를 0 으로 표시 합 니 다. 자신 과 자신 사이 에 거리 가 없 는 것 과 같 습 니 다. 역할 도 동일 합 니 다 \ (vis [cur] = true \): 이 점 은 검색 되 었 습 니 다!

이웃 접점 을 매 거 합 니 다. 만약 에 이웃 접점 을 검색 하고 현재 의 직접 거리 w 를 업데이트 할 수 있다 면 업데이트 합 니 다.즉, 하나의 행렬 로 현재 노드 가 가장 짧 은 길 을 가 는 후계 점 을 나타 낸다.검색 해 보지 않 은 것 을 발견 하면 그 점 을 처리 하 는 가장 좋 은 서브 구조 로 돌려 보 내 라.

마지막 으로 이 인접 점 을 이용 하여 다른 점 을 이완 시 킬 수 있다. 분명히 느슨 해 질 수 있 는 전 제 는 이 인접 점 이 다른 점 에 대해 이미 느슨 해 졌 다 는 것 이다.

알고리즘 종료

이루어지다

void init() {
    memset(dist, inf, sizeof(dist)); //         
    memset(suf, -1, sizeof(suf)); //           
}

void dfs(int cur) {
    dist[cur][cur] = 0; //       cost，             
    for (int i = 0; i < edge[cur].size(); i++) {
        edge& v = edge[cur][i];
        if (dist[cur][v] < v.w) { //            
            dist[cur][v] = v.w;
            suf[cur][v] = v.to; //       
        }
        if (dist[s][v] == inf) dfs(v.to); //                             
        for (int j = 1; j <= n; j++) //         
            if (dist[v.to][j] < inf) //                                   
                if (dist[cur][j] > dist[v.to][j] + v.w) {
                    dist[cur][j] > dist[v.to][j] + v.w;
                    suf[cur][j] = v.to; //           
                }
    }
}

void AllshortPaths() {
    init();
    for (int i = 1; i <= n; i++)
        if (dist[i][i] == inf)
            dfs(i);
}