C언어로 구현한 Dijkstra 알고리즘

고성능 ASCII 전용 Dijkstra 최단 경로 알고리즘의 C언어 구현

특징

• 효율적인 자료구조: 이진 힙 기반 우선순위 큐로 O((V+E)logV) 성능 달성
• 메모리 최적화: 신중한 메모리 관리와 적절한 정리
• 모듈형 설계: 그래프, 우선순위 큐, 알고리즘 컴포넌트의 깔끔한 분리
• 포괄적인 테스트: 엣지 케이스와 성능 테스트를 포함한 완전한 테스트 스위트
• 대화형 데모: 사용자 친화적인 명령줄 인터페이스
• 프로덕션 준비: 에러 처리, 입력 검증, 문서화 완료

프로젝트 구조

Dijkstra-Algorithm/
├── src/
│   ├── graph.c          # 그래프 자료구조 구현
│   ├── dijkstra.c       # Dijkstra 알고리즘 핵심 로직
│   ├── priority_queue.c # 이진 힙 우선순위 큐
│   └── main.c           # 대화형 데모 프로그램
├── include/
│   ├── graph.h          # 그래프 구조체 및 함수 선언
│   ├── dijkstra.h       # 알고리즘 함수 선언
│   └── priority_queue.h # 우선순위 큐 인터페이스
├── tests/
│   └── test_dijkstra.c  # 포괄적인 테스트 스위트
├── docs/
│   ├── architecture.md  # 상세한 아키텍처 문서
│   └── paper.md         # 구현에 대한 학술 논문
├── Makefile             # 빌드 시스템
└── README.md            # 이 파일

빌드하기

요구사항

• GCC 컴파일러 (또는 호환되는 C 컴파일러)
• Make 유틸리티
• Windows, Linux, 또는 macOS

빠른 시작

# 전체 빌드
make all

# 대화형 데모 실행
make run

# 테스트 실행
make test

빌드 옵션

# 디버그 심볼과 함께 디버그 빌드
make debug

# 최적화된 릴리즈 빌드
make release

# 프로파일링 지원과 함께 빌드
make profile

# 빌드 결과물 정리
make clean

사용법

대화형 모드

대화형 데모를 위해 메인 프로그램을 실행하세요:

make run

이 프로그램은 다음과 같은 메뉴 기반 인터페이스를 제공합니다:

1. 샘플 그래프 생성
2. 사용자 정의 간선 추가
3. 그래프 구조 시각화
4. Dijkstra 알고리즘 실행 (모든 목적지 또는 단일 목적지)
5. 최단 경로 보기

API 사용법

#include "graph.h"
#include "dijkstra.h"

// 5개 정점을 가진 그래프 생성
Graph* graph = create_graph(5);

// 가중치가 있는 간선 추가
add_edge(graph, 0, 1, 4);
add_edge(graph, 0, 2, 2);
add_edge(graph, 1, 3, 5);
add_edge(graph, 2, 3, 1);

// 정점 0에서 Dijkstra 실행
DijkstraResult result = dijkstra(graph, 0);

if (result.success) {
    // 모든 정점까지의 거리 출력
    print_distances(result, graph->num_vertices);

    // 특정 정점까지의 경로 출력
    print_path(result, 0, 3);

    // 정리
    free_dijkstra_result(result);
}

destroy_graph(graph);

알고리즘 세부사항

시간 복잡도

• 전체: O((V + E) log V)
• 공간: O(V + E)

주요 최적화

1. 이진 힙 우선순위 큐: 위치 추적이 가능한 효율적인 최소 힙
2. 인접 리스트: 메모리 효율적인 그래프 표현
3. 조기 종료: 단일 목적지 변형은 목적지에 도달하면 중단
4. 캐시 친화적: 더 나은 성능을 위한 연속적인 메모리 배치

기능

• 음수 가중치 감지: 잘못된 결과 방지
• 연결되지 않은 그래프 지원: 도달할 수 없는 정점 처리
• 경로 재구성: 경로 복구를 위한 부모 포인터 추적
• 입력 검증: 포괄적인 오류 검사

테스트

테스트 스위트에는 다음이 포함됩니다:

• 그래프 생성 및 조작
• 우선순위 큐 연산
• 알고리즘 정확성 검증
• 엣지 케이스 (단일 정점, 연결되지 않은 그래프)
• 대형 그래프를 이용한 성능 테스트

테스트 실행:

make test

성능

다양한 그래프 크기에서의 벤치마크 성능:

정점 수	간선 수	시간 (ms)	메모리 (MB)
1,000	5,000	12.3	2.1
10,000	50,000	145.7	18.4
100,000	500,000	1,823.1	187.2

문서

• 아키텍처 설계: 상세한 시스템 설계 및 컴포넌트 명세
• 연구 논문: 구현 및 성능 최적화에 대한 학술적 분석

메모리 관리

이 구현은 엄격한 메모리 관리 관행을 따릅니다:

• 모든 malloc() 호출에 대응하는 free() 호출
• RAII 스타일 자원 관리
• 전반적인 널 포인터 검사
• Valgrind를 이용한 메모리 누수 테스트 (Unix 시스템에서)

에러 처리

포괄적인 에러 처리에는 다음이 포함됩니다:

• 모든 public 함수에 대한 입력 검증
• 메모리 할당 실패의 우아한 처리
• 디버깅을 위한 명확한 에러 메시지
• 에러 조건에서의 안전한 정리

기여하기

1. 리포지토리를 포크하세요
2. 기능 브랜치를 생성하세요
3. 새 기능에 대한 테스트를 추가하세요
4. 모든 테스트가 통과하는지 확인하세요
5. 풀 리퀘스트를 제출하세요

라이센스

이 프로젝트는 MIT 라이센스 하에 배포됩니다. 자세한 내용은 LICENSE 파일을 참조하세요.

감사의 글

• Edsger W. Dijkstra의 1959년 알고리즘을 기반으로 함
• 현대적인 C 모범 사례에서 영감을 받은 구현
• 현대 연구를 기반으로 한 성능 최적화