[자료구조] 다익스트라 알고리즘 (최단경로찾기) by C++

소개글

□ 문제개요

○ 사용자로부터 정점의 개수를 입력 받아 그래프를 구성한다.
○ 사용자는 시작점과, 종료지점을 입력한다.
○ 다익스트라 알고리즘을 이용하여 시작점부터 목적지까지의 최단거리가지의 경로와 비용을 구한다

목차

- 문제의 개요
- 문제 분석 및 알고리즘
- 소스 및 주석
- 실행 화면 CAPTURE

본문내용

* 본문의 일부를 발췌

□ 분석 및 알고리즘

○ 문제분석
- 다음의 함수들을 사용한다.
a. void input() : 인접-행렬 입력 및 생성
b. void ShortestPath(const int n, const int v) : 빠른길로 가중치를 갱신
c. int choose(int) : 시작~목적지 까지의 누적 길이가 가장 적은 정점을 반환
d. void print_route(int i , int u) : 누적 길이를 출력
e. void result(int v,int end) : 최종 목적지까지의 최종 경로 출력
- row와 column 이 같은 data는 자기 자신으로의 방향이므로 ‘0’값을 자동 입력 받았다.
- 교재의 있는 LA를 찾아가는 다익스트라 예제를 test 프로그램으로 한다.

○ 알고리즘
- Dijkstra 알고리즘
출발점에서 시작하여 거리가 최소인 정점을 선택해 나가면 최단 경로를 구할 수 있다는 greedy 알고리즘
의 일종이다.
- 시작 정점에서 인접한 정점중 가장 비용이 최소인 정점을 선택하여 지나온 경로 S에 포함시킨다
- 미선택 정점중에서 선택한 최소 거리 정점 w 거리 Dist[w]는 S에서 w 까지의 최단 경로의 길이다.

- 더 짧은 새로은 길을 발견 할때 Dist[w]의 누적 길이를 갱신한다.
- 갱신시에 지나온 경로를 역추적 하기위해 previous[n] 배열에 이전 vertex를 기억한다.
- 다익스트라 작동 원리

이하생략

참고 자료

없음

압축파일 내 파일목록

dikstra.h
dikstra.hwp
main.cpp