apsp

최단 경로 문제

함수명

apsp　모든 정점으로 대하는 최단 경로 문제(All-Pairs Shortest Paths Problem, APSP 문제). 즉, 몇개의 시가 있어, 시와 시와의 사이의 거리를 알 수 있었을 때, 어느 시로부터 다른 시까지의 최단 거리를 요구하는 문제이다.

형식

void apsp(int *shortest, int *distance, int numOfCity);

인수

shortest   (출력) 최단 거리가 들어가 있는 배열
distance   (입력) 시와 시와의 직접 거리
numOfCity  (입력) 시의 수

함수치

없음

주의 사항

인수 shortest, distance 는 numOfCity X numOfCity 의 2 차원 배열의 생각으로 이용하십시오. 시에 번호 1 ~ n 를 나누어 거절했을 때,

    distance[0]            시 1으로부터 시 1까지(자기 자신에게)의 거리
    distance[1]            시 1으로부터 시 2까지의 거리
    distance[numOfCity-1]  시 1으로부터 시 n까지의 거리
    distance[numOfCity]    시 2로부터 시 1까지의 거리
    distance[numOfCity+1]  시 2로부터 시 2(자기 자신에게)의 거리

된다. 즉, numOfCity 분의 배열 요소 마다, 어느 시로부터 다른 모두 의 시에의 거리가 distance 배열에 들어가 있다.
덧붙여 자기 자신에게로의 거리는 항상 0이며, 이치마의 직접 경로가 없을 때는, 무한대의 생각으로 큰 값을 사용하면(자) 좋다.

용례

용례 프로그램(apsp-test.c )

사용법입니다만, 우선 데이터 파일을 준비해 둔다. 시의 수를 데이터 파일의 1행째에 쓴다. 2행째부터는 1행 마다 각 시간의 거리를 쓴다. 2 이치마의 직접 경로가 없을 때는, 무한대의 생각으로 큰 숫자(예를 들어 20000)을 사용한다.

    3        <-- 시의 수
    0        <-- 시 1으로부터 시 1(자기 자신)에의 거리
    20       <-- 시 1으로부터 시 2에의 거리
    20000    <-- 시 1으로부터 시 3에의 거리(직접 경로가 없기 때문에, 무한대)
    20       <-- 시 2로부터 시 1에의 거리
    0        <-- 시 2로부터 시 2(자기 자신)에의 거리
    10       <-- 시 2로부터 시 3에의 거리
    25       <-- 시 3으로부터 시 1에의 거리(편통행의 길은 있다)
    10       <-- 시 3으로부터 시 2에의 거리
    0        <-- 시 3으로부터 시 3(자기 자신)에의 거리

그리고 데이터 파일을 쓴다. 다음에, 용례 프로그램은
　　　apsp-test　데이터 파일
그리고 실행하면, 각 시간의 최단 거리가 표시된다.

프로그램(apsp.c )

void apsp(int *shortest, int *distance, int numOfCity){
    int  i, j, k;
    int  *s, *d;
    int  x;
    
    s = shortest;
    d = distance;
    for (i = 0; i < numOfCity; i++)
        for (j = 0; j < numOfCity; j++) {
            *s++ = (j ! = i) ?  *d : 0;
            d++;
        }

    for (k = 0; k < numOfCity; k++) {
        s = shortest;
        for (i = 0; i < numOfCity; i++)
            for (j = 0; j < numOfCity; j++) {
                if (*s > (x = *(shortest + i*numOfCity + k) 
                            + *(shortest + k*numOfCity + j)))
                    *s = x;
                s++;
            }
    }
}

설명

본프로그램에는 Floyd 방법을 사용하고 있다. 실행 시간은 시수의 3 승오더이다.

시 대신에 역을 생각해 거리 대신에 전철대를 생각하면(자), 이 문제는 역에서 역까지의 최저 환승 전철 운임을 요구하는 문제가 된다. 따라서, 응용범위는 실로 넓다. 최근의 카내비게이션도 그 일례일 것이다.

관련 함수