Dijkstra Practice

testcode.c

#pragma warning(disable:4996)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>    // sqrt 함수가 선언된 헤더 파일

#define INF        (1000000)

int V, E, K;
double cost[890050 + 5];
double distance[890050 + 5];
unsigned char change = 1;

typedef struct EDGE {
    int u, v;
    double w;
} EDGE;

EDGE edge[58507 + 5];

struct Node {
    int index;
    int id;
    double x;
    double y;
    struct Node *next;
};

struct ArcNode {
    int from;
    int to;
    double cost;
    struct ArcNode *next;
};

int makeLinkedList(struct Node *pNode);

int readDataFile(struct Node *prev);

void presentAllNodeData(struct Node *pNode);

void setUpArcData(struct ArcNode *head);

void readDataFileForArc(struct ArcNode *prev);

void solve(struct Node *head, struct ArcNode *pNode);

double getTwoPointsDistance(double P1x, double P1y, double P2x, double P2y);

double getTwoPointsDistance(double P1x, double P1y, double P2x, double P2y);

void presentAllArcNodeData(struct ArcNode *pNode);

int main() {
    struct Node *head = malloc(sizeof(struct Node));
    makeLinkedList(head);

    struct ArcNode *arcHead = malloc(sizeof(struct ArcNode));
    setUpArcData(arcHead);

    solve(head, arcHead);

    free(head);
    free(arcHead);

    return 0;
}

void solve(struct Node *nodesHead, struct ArcNode *arcsHead) {
    // 1번노드를 시작으로 모든 노드에 대해 그 노드로 접근하는 방법의 최소 비용을 구하기.
    // 각 노드를 거쳐가는 과정을 기록하고 그 과정을 저장해두었다가 각 거리를 구하여 총합하여 구하기.



    FILE *resultFile = fopen("result.txt", "w");

    int i = 0;
    double temp;

    V = 890050;
    E = 58507;
    K = 890050;

    //////////
    // u, v, w 는 arc 데이터로부터 가져와야 한다
    struct ArcNode *curNode = arcsHead;
    curNode = curNode->next;
    while (curNode != NULL) {
        edge[i].u = curNode->from;
        edge[i].v = curNode->to;
        edge[i].w = curNode->cost;

        curNode = curNode->next;
        i++;
    }
    //////////

    for (i = 1; i <= V; i++) cost[i] = INF;
    cost[K] = 0;
    distance[K] = 0;

    while (change) {
        change = 0;
        for (i = 0; i < E; i++) {
            if (cost[edge[i].v] > (temp = cost[edge[i].u] + edge[i].w)) {
                // 1번째 정범부터 v번째 정점까지 걸리는 cost와
                // 현재 위치인 u번째 정점까지 이동하는데 걸렸던 코스트 + u에서 v까지 이동하는데 걸리는 코스트 를 비교하여
                // 더 작으면 cost[1번에서 이동하려는 도착지 목표지점 정점 id] = temp
                // u : from / v : to
                cost[edge[i].v] = temp;
                change = 1;
            }
        }
    }

    for (i = 1; i <= V; i++) {
        if (cost[i] != INF) {
            fprintf(resultFile, "890050 to %d cost is : %.2f\n", i, cost[i]);
        }
    }

    fclose(resultFile);
}

int makeLinkedList(struct Node *head) {

    int nodeCount = readDataFile(head);
    //presentAllNodeData(head);

    return nodeCount;
}

int readDataFile(struct Node *prev) {
    char *deli = " ";
    int deliIndex = 0;
    char *pt1;
    int nowIndex = 1;

    int id = 0;
    double x = 0;
    double y = 0;

    FILE *pFile = NULL;

    pFile = fopen("dataset.txt", "r");
    if (pFile != NULL) {
        char strTemp[255];

        while (!feof(pFile)) {
            fgets(strTemp, sizeof(strTemp), pFile);

            // 한줄을 받아왔는데 그 줄의 첫번째 글자가 t면 어떤 행동을 할까,
            if (strTemp[0] == 't') {
                continue;
            } else if (strTemp[0] == ' ') {
                prev->next = NULL;
                break;
            } else {
                struct Node *newNode = malloc(sizeof(struct Node));   // 첫 번째 노드 생성

                pt1 = strtok(strTemp, deli);
                while (pt1) {
                    if (deliIndex == 1) {
                        id = atoi(pt1);
                    } else if (deliIndex == 2) {
                        x = atof(pt1);
                    } else if (deliIndex == 3) {
                        y = atof(pt1);
                    }

                    pt1 = strtok(NULL, deli);
                    deliIndex++;
                }

                prev->next = newNode;
                newNode->id = id;
                newNode->x = x;
                newNode->y = y;
                newNode->index = nowIndex;
                nowIndex++;

                prev = newNode;
            }
            deliIndex = 0;
        }

        fclose(pFile);
    } else {
        printf("[Error] Cannot read dataset.txt file.\n");
    }

    return nowIndex;
}

void presentAllNodeData(struct Node *head) {
    FILE *resultFile = fopen("result.txt", "w");

    struct Node *curNode = head;
    curNode = curNode->next;
    while (curNode != NULL) {
        printf("%d ", curNode->index);
        printf("%d ", curNode->id);
        printf("%.2f ", curNode->x);
        printf("%.2f\n", curNode->y);

        fprintf(resultFile, "%d %d %.2f %.2f\n", curNode->index, curNode->id, curNode->x, curNode->y);

        curNode = curNode->next;
    }

    fclose(resultFile);
}

void setUpArcData(struct ArcNode *head) {
    readDataFileForArc(head);
    //presentAllArcNodeData(head);
}

void readDataFileForArc(struct ArcNode *prev) {
    int meetTCount = 0;
    char *deli = " ";
    int deliIndex = 0;
    char *pt1;

    int from = 0;
    int to = 0;
    double cost = 0;

    FILE *resultFile = fopen("result.txt", "w");
    FILE *pFile = NULL;
    pFile = fopen("dataset.txt", "r");
    if (pFile != NULL) {
        char strTemp[255];

        while (!feof(pFile)) {
            char *testPt = fgets(strTemp, sizeof(strTemp), pFile);

            if (strTemp[0] == 't') {
                meetTCount++;
                continue;
            } else {
                if (meetTCount < 2) {
                    continue;
                } else {
                    // arc 데이터를 접하는 영역
                    pt1 = strtok(strTemp, deli);
                    while (pt1) {
                        if (deliIndex == 1) {
                            from = atoi(pt1);
                        } else if (deliIndex == 2) {
                            to = atoi(pt1);
                        } else if (deliIndex == 3) {
                            cost = atof(pt1);
                        }

                        pt1 = strtok(NULL, deli);
                        deliIndex++;
                    }

                    if (testPt != NULL) {
                        struct ArcNode *newNode = malloc(sizeof(struct ArcNode));   // 첫 번째 노드 생성

                        prev->next = newNode;
                        newNode->from = from;
                        newNode->to = to;
                        newNode->cost = cost;

                        prev = newNode;
                    }
                }
            }

            deliIndex = 0;
        }
        prev->next = NULL;

        fclose(pFile);
        fclose(resultFile);
    } else {
        printf("[Error] Cannot read dataset.txt file.\n");
    }
}

void presentAllArcNodeData(struct ArcNode *head) {
    FILE *resultFile = fopen("result.txt", "w");

    struct ArcNode *curNode = head;
    curNode = curNode->next;
    while (curNode != NULL) {
        printf("%d ", curNode->from);
        printf("%d ", curNode->to);
        printf("%.2f\n", curNode->cost);

        fprintf(resultFile, "%d %d %.2f\n", curNode->from, curNode->to, curNode->cost);

        curNode = curNode->next;
    }

    fclose(resultFile);
}

double getTwoPointsDistance(double P1x, double P1y, double P2x, double P2y) {
    double distance = 0.0;

    double a = P2x - P1x;    // 선 a의 길이
    double b = P2y - P1y;    // 선 b의 길이

    distance = sqrt((a * a) + (b * b));    // (a * a) + (b * b)의 제곱근을 구함

    return distance;
}