• LF몰 이벤트
  • 파일시티 이벤트
  • 서울좀비 이벤트
  • 탑툰 이벤트
  • 닥터피엘 이벤트
  • 아이템베이 이벤트
  • 아이템매니아 이벤트

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

*영*
개인인증판매자스토어
최초 등록일
2010.06.19
최종 저작일
2010.06
12페이지/파일확장자 압축파일
가격 4,000원 할인쿠폰받기
다운로드
장바구니

소개글

다음 자료는
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
*영*
판매자 유형Bronze개인인증

주의사항

저작권 자료의 정보 및 내용의 진실성에 대하여 해피캠퍼스는 보증하지 않으며, 해당 정보 및 게시물 저작권과 기타 법적 책임은 자료 등록자에게 있습니다.
자료 및 게시물 내용의 불법적 이용, 무단 전재∙배포는 금지되어 있습니다.
저작권침해, 명예훼손 등 분쟁 요소 발견 시 고객센터의 저작권침해 신고센터를 이용해 주시기 바랍니다.
환불정책

해피캠퍼스는 구매자와 판매자 모두가 만족하는 서비스가 되도록 노력하고 있으며, 아래의 4가지 자료환불 조건을 꼭 확인해주시기 바랍니다.

파일오류 중복자료 저작권 없음 설명과 실제 내용 불일치
파일의 다운로드가 제대로 되지 않거나 파일형식에 맞는 프로그램으로 정상 작동하지 않는 경우 다른 자료와 70% 이상 내용이 일치하는 경우 (중복임을 확인할 수 있는 근거 필요함) 인터넷의 다른 사이트, 연구기관, 학교, 서적 등의 자료를 도용한 경우 자료의 설명과 실제 자료의 내용이 일치하지 않는 경우

이런 노하우도 있어요!더보기

최근 본 자료더보기
탑툰 이벤트
  다익스트라 알고리즘 버스역 프로젝트 A+자료
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
AI 챗봇
2024년 06월 18일 화요일
AI 챗봇
안녕하세요. 해피캠퍼스 AI 챗봇입니다. 무엇이 궁금하신가요?
4:40 오전
New

24시간 응대가능한
AI 챗봇이 런칭되었습니다. 닫기