13. 그래프-다익스트라의 최단 경로

다익스트라의 최단 경로

• Dijkstra's Shortest Path Algorithm은 프림 알고리즘과 흡사
• 각 간선에 대한 정보를 우선순위 큐에 담아 처리
• 음의 간선이 없을 때 정상 동작하며 현실에서는 음의 간선이 없어 적합한 알고리즘

다익스트라 과정

1. 그래프의 시작점을 선택하여 트리 T에 포함
2. T에 포함된 노드와 포함되지 않은 노드 사이의 간선 중 '이동 거리'가 가장 작은 간선 탐색
3. 해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함
4. 모든 노드가 포함될 때까지 반복

다익스트라 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define NODE_MAX 20001
#define EDGE_MAX 600001 // 양방향 간선이므로 300,000 개 * 2

// 간선구조체 정의
typedef struct {
    int cost;
    int node;
} Edge;

// 교환 함수
void swap(Edge* a, Edge* b) {
    Edge temp;
    temp.cost = a->cost;
    temp.node = a->node;
    a->cost = b->cost;
    a->node = b->node;
    b->cost = temp.cost;
    b->node = temp.node;
}

// 우선 순위 큐
typedef struct {
    Edge* heap[EDGE_MAX];
    int count;
} priorityQueue;

// 삽입 함수
void push(priorityQueue* pq, Edge* edge) {
    if (pq->count >= EDGE_MAX) return;
    pq->heap[pq->count] = edge;
    int now = pq->count;
    int parent = (pq->count - 1) / 2;

    // 새 원소 삽입 후 상향식으로 힙 구성
    while (now > 0 && pq->heap[now]->cost < pq->heap[parent]->cost) {
        swap(pq->heap[now], pq->heap[parent]);
        now = parent;
        parent = (parent - 1) / 2;
    }
    pq->count++;
}

// 추출 함수
Edge* pop(priorityQueue* pq) {
    if (pq->count <= 0)return NULL; // 더 이상 추출할 것이 없을 경우
    Edge* res = pq->heap[0]; // 루트 노드 값을 담아 둠
    pq->count--;
    pq->heap[0] = pq->heap[pq->count]; // 마지막 원소를 루트 노드로 넣음
    int now = 0, leftChild = 1, rightChild = 2;
    int target = now;

    // 새 원소 추출 후 하향식으로 힙 구성
    while (leftChild < pq->count) {
        if (pq->heap[target]->cost > pq->heap[leftChild]->cost)target = leftChild;
        if (pq->heap[target]->cost > pq->heap[rightChild]->cost&& rightChild < pq->count) target = rightChild;
        if (target == now) break; // 더 이상 내려가지 않아도 될 때 종료
        else {
            swap(pq->heap[now], pq->heap[target]);
            now = target;
            leftChild = now * 2 + 1;
            rightChild = now * 2 + 2;
        }
    }
    return res;
}

// 간선 연결 리스트 구현
typedef struct Node {
    Edge* data;
    struct Node* next;
} Node;

Node** adj;
int ans[NODE_MAX];

void addNode(Node** target, int index, Edge* edge) {
    if (target[index] == NULL) {
        target[index] = (Node*)malloc(sizeof(Node));
        target[index]->data = edge;
        target[index]->next = NULL;
    }
    else {
        Node* node = (Node*)malloc(sizeof(Node));
        node->data = edge;
        node->next = target[index];
        target[index] = node;
    }
}

// main
int main(void) {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    adj = (Node**)malloc(sizeof(Node*) * (n + 1));
    for (int i = 1;i <= n;i++) {
        adj[i] = NULL;
        ans[i] = INT_MAX;
    }

    priorityQueue* pq;
    pq = (priorityQueue*)malloc(sizeof(priorityQueue));
    pq->count = 0;

    for (int i = 0;i < m;i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        Edge* edge = (Edge*)malloc(sizeof(Edge));
        edge->node = b;
        edge->cost = c;
        addNode(adj, a, edge);
    }

    // 다익스트라 알고리즘 시작
    ans[k] = 0;
    Edge* start = (Edge*)malloc(sizeof(Edge));
    start->cost = 0;
    start->node = k;
    push(pq, start);

    while (1) {
        Edge* now = pop(pq);
        if (now == NULL) break;

        int curNode = now->node;
        int curCost = now->cost;

        if (ans[curNode] < curCost) continue;
        Node* cur = adj[curNode];

        while (cur != NULL) {
            Edge* temp = cur->data;
            temp->cost += curCost;
            if (temp->cost < ans[temp->node]) {
                ans[temp->node] = temp->cost;
                push(pq, temp);
            }
            cur = cur->next;
        }
    }

    for (int i = 1; i <= n;i++) {
        if (ans[i] == INT_MAX) printf("INF\n");
        else printf("%d\n", ans[i]);
    }

    system("pause");
    return 0;
}