플 로 이 드 에 대한 약간의 정리

910 단어
플 로 이 드 는 가장 짧 은 경로 에서 가장 간단 한 알고리즘 을 구 한 셈 이다. 이 는 보통 방향 망 (또는 무 방향 망) 을 구 하 는 데 사용 되 는데 모든 정점 vi 는 vj 와 같 지 않 고 vi 와 vj 간 의 가장 짧 은 경로 와 가장 짧 은 경로 의 길 이 를 구 해 야 한다.dijkstra 를 사용 하면 n 회 순환 해 야 합 니 다. floyd 를 사용 하면 시간 복잡성 이 줄 지 않 았 지만 o (n ^ 3) 이지 만 쓰기 가 더 간단 합 니 다.
이 안 에는 특별히 할 말 이 없 는데, 주의해 야 할 것 은 그의 두 가지 전달 공식 이다.
A^k[i][j]=min{A^(k-1)[i][j],A^(k-1)[i][k]+A^(k-1)[k][j]}  이 공식 은 항상 제목 안에서 변형 을 한다. 예 를 들 어 그 min 을 max 로 바 꾸 는 등 이다.
다음은 코드 입 니 다.
         
for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
          for(int j=0;j<n;j++)
           {
                     dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); 
            }

그러나 가끔 은 문제 가 경로 의 길 이 를 요구 하지 않 아 도 된다. 그 가 요구 하 는 것 은 가장 짧 은 경로 에 어떤 점 이 있 는 지, 이것 은 체 내 를 순환 하 는 문구 로 바 꿀 수 있다.
                                       dis[i][j]=dis[i][j]||(dis[i][k]&&dis[k][j]);
Codeforces - D. Make The Fence Great Again
memcached 완전 해부 3 - 분포 식 알고리즘

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage