다익스트라 알고리즘 버스역 프로젝트 A+자료

소개글

다음 자료는
Dijkstra`s algorithm을 이용하여 최단경로를 구합니다.
버스역을 잡고 프로젝트를 진행하였습니다.
A+ 자료입니다.

목차

최단경로(Shortest Path)
프로젝트 제안서
프로젝트 중간보고서
프로젝트 결과보고서

본문내용

1. 최단경로란?

(1) 최단 경로 : 두 정점을 연결하는 간선들의 가중치의 합이 최소인 경로를 말한다.
(2) 최단 경로 문제 : 한 가중치 그래프에서 주어진 두 정점 x와 y를 연결하는 경로 상의 모든 선분들의 가중치 합이 최소인 성질을 갖는 경로를 찾는 것이다.
(3) 최단 경로 기법 :
➀ 그리디(Greedy) 알고리즘인 다익스트라(Dijkstra) 알고리즘
➁ 동적계획법(Dynamic Programming)인 플로이드(Floyd) 알고리즘
(4) 최단경로가 사용되는 예 :
➀ GPS를 이용한 네비게이션 시스템
➁ 지하철 노선도 최단경로 검색 시스템
➂ 수송 시스템

2. 다익스트라(Dijkstra) 알고리즘

(1) 다익스트라 알고리즘이란?
- 그리디 알고리즘은 전후 상황을 파악하지 않고, 현재 시점에서 가장 최적의 상황을 찾아 경로를 파악해 나가는 것이다. 즉 최적 해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하게 된다.
- 그리디 알고리즘을 기본적 원리로 두어 최단경로를 구해내는 방법이 다익스트라 알고리즘이다. 여기서 다익스트라는 만든 사람의 이름을 딴 것이다.

(2) 다익스트라 알고리즘의 원리
- 다익스트라 알고리즘을 구체적으로 적용하기 전에 해결과정을 정리해 보면 다음과 같다.
① 가중치인접행렬에서는 직접 연결된 것이 없으면 무한대, 연결된 간선은 가중치를 표현한다.
② 두개의 집합 S와 C를 만들어 S에는 출발점을 초기값으로, C는 출발점을 제외한 모든 정점을 초기값으로 한다.
③ S에서 정해진 초기값으로부터 C의 각 정점에 대한 최단 경로 dist[i]를 구한다.
④ dist[i]의 기록 중에서 최단 경로를 택하여 해당 정점 v를 C에서 제거 후 S에 넣는다.
⑤ S의 초기 정점과 C에 직접 이르는 거리와 S안의 모든 정점을 거친 후 C에 이르는 거리중 최단 경로를 dist[w]로 한다.
⑥ ➃-➄의 과정을 C가 공집합이 될 때까지 반복한다.

참고 자료

FOUNDATION OF 알고리즘

압축파일 내 파일목록

최단경로09.hwp
프로젝트제안서.hwp
프로젝트 중간보고서.hwp
프로젝트 결과보고서.hwp
dijstra/dijstra/Debug/BuildLog.htm
dijstra/dijstra/Debug/dijstra.exe.embed.manifest
dijstra/dijstra/Debug/dijstra.pch
dijstra/dijstra/Debug/stdafx.obj
dijstra/dijstra/Debug/vc90.idb
dijstra/dijstra/Debug/vc90.pdb
dijstra/dijstra/dijstra.cpp
dijstra/dijstra/dijstra.vcproj
dijstra/dijstra/dijstra.vcproj.HAN.han.user
dijstra/dijstra/ReadMe.txt
dijstra/dijstra/stdafx.cpp
dijstra/dijstra/stdafx.h
dijstra/dijstra/targetver.h
dijstra/dijstra.ncb
dijstra/dijstra.sln
dijstra/dijstra.suo

전체 목록 보기