[알고리즘] ep7++) 다익스트라 확장 알고리즘

다익스트라 확장 알고리즘은 기본 다익스트라 알고리즘을 수정하여 단일 출발점에서 목표 지점까지의 최단 경로뿐만 아니라 최단 경로의 수까지 계산할 수 있도록 한다. 이 문제에서 요구하는 것은 다익스트라 알고리즘을 사용하여 각 정점까지의 최단 거리를 계산하고, 동시에 각 정점에 도달하는 최단 경로의 수를 세는 기능을 추가한 것이다.

 

 

샘플 그래프 G

위 샘플그래프 G에 대해 아래 정점쌍 4개를 s(ource) 및 t(arget) 인자쌍으로 각각 사용하여 수행하라(즉, 프로그램을 4회 수행함).

각 수행 결과는 아래 예시처럼 인쇄할 것

 

[출력예시]

source    target    최단거리    최단경로 수

C             A            1                 1

C             F            9                3

F             C            9                3

B             D           12               5

 

 

(주의)

1) 위 샘플그래프 G는 프로그램 수행 초기에 인접리스트 구조로 초기화된 이후 Dijkstra 확장 알고리즘 수행에 사용되어야 함.

2) G는 단지 6개의 정점과 9개의 간선만을 포함하지만, 이보다 훨씬 많은 수의 정점과 간선을 포함하는 그래프로 대체되더라도 Dijkstra 확장 알고리즘은 아무 수정 없이 그대로 사용될 수 있도록 작성해야 함.

 

 

 

 

 

(전체코드)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct VERTEX {
    char name; // 정점 이름
    int minDistance; // 최단 거리
    int pathCnt; // 최단 경로의 수
    struct VERTEX* next; // 다음 정점 포인터
    struct INCIDENCE* incidence; // 인접한 간선 리스트 포인터
} VERTEX;

// 간선에 대한 정보 저장하는 구조체 정의
typedef struct INCIDENCE {
    struct EDGE* edge; // 연결된 간선 포인터
    struct INCIDENCE* next; // 다음 간선 포인터
} INCIDENCE;

typedef struct EDGE {
    int w; // 간선의 가중치
    struct VERTEX* leftV; // 간선의 왼쪽 정점
    struct VERTEX* rightV; // 간선의 오른쪽 정점
    struct EDGE* next; // 다음 간선 포인터
} EDGE;

// 힙 구조체 정의 (우선순위 큐)
typedef struct HEAP {
    VERTEX* v; // 힙에 저장된 정점
    int priority; // 정점의 우선순위 (거리)
} HEAP;

VERTEX* g_headV = NULL; // 정점 리스트의 시작 포인터
EDGE* g_headE = NULL; // 간선 리스트의 시작 포인터

void createVertex(char name);
void createEdge(char leftName, char rightName, int w);
VERTEX* getOppositeVertex(VERTEX* u, INCIDENCE* e); // 주어진 간선에서 반대편 정점을 반환하는 함수

void push(HEAP* heap, int* heapSize, VERTEX* v, int priority); // 힙에 요소 추가 함수
VERTEX* pop(HEAP* heap, int* heapSize); // 힙에서 최소 우선순위 요소 제거 함수
void heapifyDown(HEAP* heap, int heapSize, int index); // 힙 정렬 함수 (downheap)
void heapifyUp(HEAP* heap, int heapSize, int index); // 힙 정렬 함수 (upheap)
void extendedDijkstra(char search, char target); // SSSTC: Single Source Shortest Path with Target Counting
void freeGraph();

int main() {
    for (char i = 'A'; i <= 'F'; i++) { // 정점 A부터 F까지 생성
        createVertex(i);
    }
    createEdge('A', 'B', 8);
    createEdge('A', 'C', 1);
    createEdge('A', 'D', 4);
    createEdge('B', 'C', 7);
    createEdge('B', 'E', 4);
    createEdge('C', 'D', 5);
    createEdge('C', 'E', 3);
    createEdge('C', 'F', 9);
    createEdge('D', 'F', 4);

    // 다익스트라 알고리즘으로 최단 경로 및 경로 수 찾기
    printf("source    target    최단거리    최단경로 수\n");
    char search, target;
    while (1) { // 인자쌍 입력 받기 (빈 문자열 입력 시 종료)
        scanf("%c %c", &search, &target);
        getchar();
        if (search == "" && target == "") {
            break;
        }

        extendedDijkstra(search, target);
    }

    freeGraph();
    return 0;
}

void createVertex(char name) {
    VERTEX* newNode = (VERTEX*)malloc(1 * sizeof(VERTEX));
    newNode->name = name; // 정점 이름 설정
    newNode->minDistance = 2147483647; // 초기 최단 거리는 무한
    newNode->pathCnt = 0; // 초기 최단 경로 수는 0
    newNode->next = g_headV; // 새 정점은 현재 헤드를 가리킴
    newNode->incidence = NULL; // 인접 간선 리스트는 NULL로 초기화
    g_headV = newNode; // 헤드는 새로운 정점을 가리킴
}

void createEdge(char leftName, char rightName, int w) {
    EDGE* newNode = (EDGE*)malloc(1 * sizeof(EDGE));
    newNode->w = w; // 간선의 가중치 설정
    newNode->next = g_headE; // 새 간선은 현재 헤더를 가리킴
    g_headE = newNode; // 헤더는 새로운 간선을 가리킴

    // leftN과 rightN에 해당하는 정점 찾기
    VERTEX* leftV = g_headV;
    VERTEX* rightV = g_headV;
    while (leftV && leftV->name != leftName) {
        leftV = leftV->next;
    }
    while (rightV && rightV->name != rightName) {
        rightV = rightV->next;
    }
    newNode->leftV = leftV; // 간선의 왼쪽 정점 설정
    newNode->rightV = rightV; // 간선의 오른쪽 정점 설정

    // 왼쪽 정점의 인접 리스트에 간선 추가
    INCIDENCE* newInc = (INCIDENCE*)malloc(1 * sizeof(INCIDENCE));
    newInc->edge = newNode;
    newInc->next = leftV->incidence;
    leftV->incidence = newInc;

    // 오른쪽 정점의 인접 리스트에 간선 추가
    newInc = (INCIDENCE*)malloc(1 * sizeof(INCIDENCE));
    newInc->edge = newNode;
    newInc->next = rightV->incidence;
    rightV->incidence = newInc;
}

// 주어진 간선에서 반대편 정점을 반환하는 함수
VERTEX* getOppositeVertex(VERTEX* u, INCIDENCE* e) {
    EDGE* temp = e->edge;
    return (temp->leftV == u) ? temp->rightV : temp->leftV;
}

// 힙에 요소를 추가하는 함수
void push(HEAP* heap, int* heapSize, VERTEX* v, int priority) {
    heap[*heapSize].v = v; // 정점 추가
    heap[*heapSize].priority = priority; // 우선순위 설정
    heapifyUp(heap, *heapSize, (*heapSize)++); // 힙 정렬
}

// 힙에서 최소 우선순위 요소를 제거하고 반환하는 함수
VERTEX* pop(HEAP* heap, int* heapSize) {
    if (*heapSize == 0) {
        return NULL; // 힙이 비어 있으면 NULL 반환
    }
    VERTEX* min = heap[0].v; // 최소 우선순위 정점
    heap[0] = heap[--(*heapSize)]; // 마지막 요소를 루트로 이동
    heapifyDown(heap, *heapSize, 0); // 힙 정렬
    return min; // 최소 정점 반환
}

// 힙을 정렬하는 함수 (downheap)
void heapifyDown(HEAP* heap, int heapSize, int index) {
    int leftChildIdx = 2 * index + 1;
    int rightChildIdx = 2 * index + 2;
    int smallerIdx = index;

    // 왼쪽 자식과 비교
    if (leftChildIdx < heapSize && heap[leftChildIdx].priority < heap[smallerIdx].priority) {
        smallerIdx = leftChildIdx;
    }
    // 오른쪽 자식과 비교
    if (rightChildIdx < heapSize && heap[rightChildIdx].priority < heap[smallerIdx].priority) {
        smallerIdx = rightChildIdx;
    }
    // 현재 인덱스와 교환
    if (smallerIdx != index) {
        HEAP temp = heap[index];
        heap[index] = heap[smallerIdx];
        heap[smallerIdx] = temp;
        heapifyDown(heap, heapSize, smallerIdx);
    }
}

// 힙을 정렬하는 함수 (upheap)
void heapifyUp(HEAP* heap, int heapSize, int index) {
    int parent = (index - 1) / 2;
    if (index > 0 && heap[index].priority < heap[parent].priority) {
        HEAP temp = heap[index];
        heap[index] = heap[parent];
        heap[parent] = temp;
        heapifyUp(heap, heapSize, parent);
    }
}

// SSSTC: Single Source Shortest Path with Target Counting
void extendedDijkstra(char search, char target) {
    // 모든 정점의 거리와 경로 수 초기화
    VERTEX* p = g_headV;
    while (p != NULL) {
        p->minDistance = 2147483647;
        p->pathCnt = 0;
        p = p->next;
    }
    // 시작 정점 찾기
    VERTEX* s = g_headV;
    while (s != NULL) {
        if (s->name == search) {
            break;
        }
        s = s->next;
    }
    s->minDistance = 0;
    s->pathCnt = 1; // 시작 정점의 경로 수는 1로 설정

    HEAP heap[10000];
    int heapSize = 0;
    push(heap, &heapSize, s, 0); // 시작 정점을 힙에 추가

    while (heapSize > 0) {
        VERTEX* u = pop(heap, &heapSize); // 최소 거리 정점 꺼내기
        INCIDENCE* e = u->incidence;
        while (e != NULL) {
            VERTEX* v = getOppositeVertex(u, e);
            int new_dist = u->minDistance + e->edge->w;
            if (new_dist < v->minDistance) { // 새로운 최단 경로 발견 시 경로 수 갱신
                v->minDistance = new_dist;
                v->pathCnt = u->pathCnt;
                push(heap, &heapSize, v, new_dist);
            }
            else if (new_dist == v->minDistance) { // 최단 거리 동일 시 경로 수 누적
                v->pathCnt += u->pathCnt;
            }
            e = e->next;
        }
    }

    // 목표 정점의 최단 거리와 경로 수 출력
    VERTEX* t = g_headV;
    while (t != NULL) {
        if (t->name == target) {
            printf("%-9c %-9c %-11d %-9d\n", search, target, t->minDistance, t->pathCnt);
        }
        t = t->next;
    }
}

// 그래프 메모리 해제 함수
void freeGraph() {
    // 정점 리스트 메모리 해제
    VERTEX* p = g_headV;
    while (p != NULL) {
        VERTEX* tmpV = p;
        p = p->next;
        INCIDENCE* tmpI = tmpV->incidence;
        while (tmpI != NULL) {
            INCIDENCE* tmpIi = tmpI;
            tmpI = tmpI->next;
            free(tmpIi);
        }
        free(tmpV);
    }

    // 간선 리스트 메모리 해제
    EDGE* q = g_headE;
    while (q != NULL) {
        EDGE* tmpE = q;
        q = q->next;
        free(tmpE);
    }
}

 

 

 

 

 

 

 

 

출처 및 참고: 알고리즘-원리와 응용(국형준교수님)