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

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

*세*
최초 등록일
2011.02.18
최종 저작일
2010.07
10페이지/파일확장자 압축파일
가격 3,000원 할인쿠폰받기
다운로드
장바구니

소개글

□ 문제개요

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

목차

- 문제의 개요
- 문제 분석 및 알고리즘
- 소스 및 주석
- 실행 화면 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

자료후기(1)

*세*
판매자 유형Bronze개인

주의사항

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

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

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

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

최근 본 자료더보기
  • 해남 꿀고구마
탑툰 이벤트
[자료구조] 다익스트라 알고리즘 (최단경로찾기) by C++
에브리타임 이벤트 lf몰이벤트 신한 체크카드 오늘 하루 보지 않기 닫기