Dijkstra 최 단 로 알고리즘

이 어 전편 에서 이번 의 가장 짧 은 길 은 Dijkstra 알고리즘 을 사용 한 것 으로 여전히 그 큰 신의...
지난주 에 우 리 는 신기 한 다섯 줄 밖 에 없 는 Floyd 최 단 로 알고리즘 을 소 개 했 는데 이것 은 '다 원 최 단 로' 라 고 불 린 다.이번 주 에 하나의 점 (원점) 을 지정 하여 다른 각 정점 까지 의 가장 짧 은 경 로 를 소개 하 는데 이것 은 '단원 최 단 경로' 라 고도 부른다.예 를 들 어 다음 그림 의 1 번 정점 에서 2, 3, 4, 5, 6 번 정점 까지 의 가장 짧 은 경 로 를 구 합 니 다.
 
       Floyd - Warshall 알고리즘 과 마찬가지 로 2 차원 배열 e 를 사용 하여 정점 간 의 관 계 를 저장 합 니 다. 초기 값 은 다음 과 같 습 니 다.
 
       우 리 는 1 차원 배열 dis 로 1 번 정점 에서 나머지 각 정점 까지 의 초기 거 리 를 저장 해 야 한다. 다음 과 같다.
 
       우 리 는 이때 dis 배열 의 값 을 최 단 로 의 '평가 값' 이 라 고 부른다.
 
       1 번 정점 에서 나머지 각 정점 까지 의 가장 짧 은 거 리 를 구 하 는 만큼 1 번 정점 에서 가장 가 까 운 정점 을 찾 아 보 자.배열 dis 를 통 해 현재 1 번 정점 에서 가장 가 까 운 것 이 2 번 정점 임 을 알 수 있 습 니 다.2 번 정점 을 선택 한 후에 dis [2] 의 값 은 '평가 치' 에서 '확정 치' 로 바 뀌 었 다. 즉, 1 번 정점 에서 2 번 정점 까지 의 가장 짧 은 거 리 는 현재 dis [2] 값 이다.왜 일 까요?생각해 보 세 요. 현재 1 번 정점 에서 가장 가 까 운 것 은 2 번 정점 입 니 다. 그리고 이 그림 의 모든 변 은 양수 입 니 다. 그러면 세 번 째 정점 을 통 해 중 전 될 수 없 을 것 입 니 다. 1 번 정점 에서 2 번 정점 까지 의 거 리 를 더욱 단축 시 킬 수 있 습 니 다.왜냐하면 1 번 정점 에서 다른 정점 까지 의 거 리 는 1 번 에서 2 번 정점 까지 짧 지 않 을 거 예요. 그 렇 죠 O (∩ ∩) O ~
 
       2 번 정점 을 선택 한 이상 2 번 정점 에 어떤 아웃 이 있 는 지 살 펴 보 자.2 - > 3 과 2 - > 4 두 변 이 있 습 니 다.먼저 2 - > 3 이 변 을 통 해 1 번 정점 에서 3 번 정점 까지 의 거 리 를 짧게 할 수 있 는 지 토론 합 니 다.즉, 지금 디 스 [3] 와 디 스 [2] + e [2] 의 크기 를 비교 해 보 자.그 중에서 dis [3] 는 1 번 정점 에서 3 번 정점 까지 의 거 리 를 나타 낸다.dis [2] + e [2] [3] 에서 dis [2] 는 1 번 정점 에서 2 번 정점 까지 의 거 리 를 나타 내 고 e [2] [3] 은 2 - > 3 변 을 나타 낸다.그래서 dis [2] + e [2] [3] 는 1 번 정점 에서 2 번 정점 까지 2 - > 3 쪽 을 통 해 3 번 정점 까지 의 거 리 를 나타 낸다.
 
       우 리 는 dis [3] = 12, dis [2] + e [2] [3] = 1 + 9 = 10, dis [3] > dis [2] + e [2] [3] 를 발 견 했 기 때문에 dis [3] 는 10 으로 업데이트 해 야 한다.이 과정 에는 이완 이라는 전문 용어 가 있다.즉, 1 번 정점 에서 3 번 정점 까지 의 거 리 는 dis [3] 이 고 2 - > 3 을 통 해 이완 에 성공 했다.이것 이 바로 Dijkstra 알고리즘 의 주요 사상 이다. '변' 을 통 해 1 번 정점 에서 나머지 각 정점 까지 의 거 리 를 늦 추 는 것 이다.
 
       같은 이치 로 2 - > 4 (e [2] [4]) 를 통 해 dis [4] 의 값 을 표시 이완 에서 4 (dis [4] 초기 에 표시, dis [2] + e [2] [4] = 1 + 3 = 4, dis [4] > dis [2] + e [2] [4] 로 할 수 있 기 때문에 dis [4] 는 4 로 업데이트 해 야 한다.
 
       방금 우 리 는 2 번 정점 의 모든 출입 을 느슨하게 했다.이완 이 끝 난 후 dis 배열 은:
 
       이 어 나머지 3, 4, 5, 6 번 정점 에서 1 번 정점 에서 가장 가 까 운 정점 을 계속 선택한다.위 를 통 해 dis 배열 을 업데이트 한 적 이 있 습 니 다. 현재 1 번 정점 에서 가장 가 까 운 것 은 4 번 정점 입 니 다.이때 dis [4] 의 값 은 '추정 값' 에서 '확정 값' 으로 바 뀌 었 다.다음은 4 번 정점 의 모든 출 변 (4 - > 3, 4 - > 5 와 4 - > 6) 을 아까 의 방법 으로 이완 시킨다.이완 이 끝 난 후 dis 배열 은:
 
       계속해서 남 은 3, 5, 6 번 정점 중 1 번 정점 에서 가장 가 까 운 정점 을 골 라 이번 에는 3 번 정점 을 선택한다.이때 dis [3] 의 값 은 '추정 값' 에서 '확정 값' 으로 바 뀌 었 다.3 번 정점 의 모든 아웃 사 이 드 (3 - > 5) 를 이완 시킨다.이완 이 끝 난 후 dis 배열 은:
 
       계속해서 남 은 5 와 6 번 정점 중 1 번 정점 에서 가장 가 까 운 정점 을 고 르 고, 이번 에는 5 번 정점 을 선택한다.이때 dis [5] 의 값 은 '추정 값' 에서 '확정 값' 으로 바 뀌 었 다.5 번 정점 의 모든 아웃 사 이 드 (5 - > 4) 를 이완 시킨다.이완 이 끝 난 후 dis 배열 은:
 
       마지막 으로 6 번 정점 에 있 는 모든 점 을 이완 시킨다.이 예 에서 6 번 정점 이 나 오지 않 았 기 때문에 처리 할 필요 가 없다.여기 서 dis 배열 의 모든 값 은 '추정 값' 에서 '확정 값' 으로 바 뀌 었 습 니 다.
 
       최종 dis 배열 은 다음 과 같 습 니 다. 이것 이 바로 1 번 정점 에서 나머지 각 정점 까지 의 가장 짧 은 경로 입 니 다.
 
       OK, 이제 아까 알고리즘 을 정리 해 보 겠 습 니 다.알고리즘 의 기본 사상 은 매번 이 원점 (상기 예 의 원점 은 1 번 정점) 에서 가장 가 까 운 정점 을 찾 은 다음 에 이 정점 을 중심 으로 확장 하여 최종 적 으로 원점 에서 나머지 모든 점 까지 의 가장 짧 은 경 로 를 얻 는 것 이다.기본 절 차 는 다음 과 같다.
 

모든 정점 을 두 부분 으로 나눈다. 가장 짧 은 거리의 정점 집합 P 와 가장 짧 은 경 로 를 알 수 없 는 정점 집합 Q.처음에 가장 짧 은 경 로 를 알 고 있 는 정점 집합 P 에는 원점 의 정점 만 있 었 다.우 리 는 집합 P 에 어떤 점 이 있 는 지 책 [i] 배열 로 기록 합 니 다.예 를 들 어 특정한 정점 i 에 대해 책 [i] 이 1 이면 이 정점 은 집합 P 에 있 고 책 [i] 가 0 이면 이 정점 은 집합 Q 에 있다 는 것 을 나타 낸다.

원점 s 를 자신의 가장 짧 은 경로 로 0 즉 dis = 0 으로 설정 합 니 다.원점 에 직접 도착 할 수 있 는 정점 i 가 존재 하면 dis [i] 를 e [s] [i] 로 설정 합 니 다.동시에 모든 다른 (원점 에서 직접 도착 할 수 없 는) 정점 의 가장 짧 은 경 로 를 표시 로 설정 했다.

집합 Q 의 모든 정점 에서 원점 s 에서 가장 가 까 운 정점 u (즉 dis [u] 최소) 를 선택 하여 집합 P 에 가입 합 니 다.그리고 점 u 를 기점 으로 하 는 모든 변 을 고찰 하고 각 변 에 대해 느슨 한 조작 을 한다.예 를 들 어 u 에서 v 까지 의 변 이 존재 한다 면 변 u - > v 를 끝부분 에 추가 하여 s 에서 v 까지 의 경 로 를 넓 힐 수 있다. 이 경로 의 길 이 는 dis [u] + e [u] [v] 이다.만약 이 값 이 현재 알려 진 dis [v] 의 값 보다 작다 면, 우 리 는 현재 dis [v] 의 값 을 새 값 으로 대체 할 수 있 습 니 다.

3 단 계 를 반복 하고 집합 Q 가 비어 있 으 면 알고리즘 이 끝 납 니 다.최종 dis 배열 의 값 은 원점 에서 모든 정점 까지 의 가장 짧 은 경로 입 니 다.

 
       완전한 Dijkstra 알고리즘 코드 는 다음 과 같 습 니 다.
 

#include 
int main()
{
    int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,min;
    int inf=99999999; // inf(infinity   )             
    //  n m，n      ，m      
    scanf("%d %d",&n,&m);
                                                                  
    //   
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i==j) e[i][j]=0;
              else e[i][j]=inf;
                                                                            
    //   
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&t1,&t2,&t3);
        e[t1][t2]=t3;
    }
    //   dis  ，   1               
    for(i=1;i<=n;i++)
        dis[i]=e[1][i];
    //book     
    for(i=1;i<=n;i++)
        book[i]=0;
    book[1]=1;
                                                                  
    //Dijkstra      
    for(i=1;i<=n-1;i++)
    {
        //   1        
        min=inf;
        for(j=1;j<=n;j++)
        {
            if(book[j]==0 && dis[j]dis[u]+e[u][v])
                    dis[v]=dis[u]+e[u][v];
            }
        }
    }
                                                                  
    //       
    for(i=1;i<=n;i++)
        printf("%d ",dis[i]);
                                                                      
    getchar();
    getchar();
    return 0;
}

 
       다음 데 이 터 를 입력 하여 검증 할 수 있 습 니 다.첫 줄 두 정수 n m。n 은 정점 개수 (정점 번 호 는 1 ~ n) 를 나타 내 고 m 는 변 의 수 를 나타 낸다.다음 m 줄 은 줄 당 3 개의 x y z 가 있다 는 것 을 나타 낸다.정점 x 에서 정점 y 변 까지 의 가중치 가 z 임 을 나타 낸다.

6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4

       실행 결 과 는?

0 1 8 4 13 17

   위의 코드 를 통 해 우 리 는 이 알고리즘 의 시간 복잡 도 는 O (N2) 임 을 알 수 있다.그 중에서 1 번 정점 에서 가장 가 까 운 정점 을 찾 을 때마다 시간 복잡 도 는 O (N) 이다. 여기 서 우 리 는 '쌓 기' (나중에 다시 말 하기) 로 최적화 시 켜 이 부분의 시간 복잡 도 를 O (logN) 로 낮 출 수 있다.또한 변수 M 이 N2 보다 적은 희소 도 (우 리 는 M 이 N2 보다 훨씬 작은 그림 을 희소 도 라 고 부 르 고 M 이 상대 적 으로 큰 그림 을 조밀도 라 고 부른다) 에 대해 우 리 는 인접 표 (이것 은 신마 의 것 입 니까? 조급해 하지 마 세 요. 다음 주 에 다시 자세히 설명 하 겠 습 니 다) 로 인접 행렬 을 대체 하여 전체 시간의 복잡 도 를 O (M + N) logN) 로 최적화 시 킬 수 있 습 니 다.주의 하 세 요!최 악의 경우 M 이 N2 인 데, 이렇게 되면 M logN 이 N2 보다 더 크다.그러나 대부분의 경우 그렇게 다 자간 이 없 기 때문에 (M + N) logN 은 N2 보다 훨씬 작다.
옮 겨 싣 기 를 환영 합 니 다. 코드 가 쉽 지 않 습 니 다. 옮 겨 싣 기 번 거 로 움 은 출처 [아하! 알고리즘] 시리즈 7: Dijkstra 최 단 로 알고리즘 을 표시 합 니 다.http://ahalei.blog.51cto.com/4767671/1387799