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

최단경로를 구하는 Dijkstra의 알고리즘 구현

*하*
개인인증판매자스토어
최초 등록일
2012.11.30
최종 저작일
2009.09
13페이지/한글파일 한컴오피스
가격 3,500원 할인쿠폰받기
다운로드
장바구니

소개글

c언어로 최단경로를 구하는 Dijkstra의 알고리즘을 구현 한 것입니다.
코드 및 분석까지 완벽한 보고서 입니다.
코드 포함 되어있습니다.

목차

없음

본문내용

▣ 문제 분석 : 최단경로를 구하는 Dijkstra의 알고리즘 구현
▶ 최단 경로를 구하는 Dijkstra의 알고리즘을 구현해 본다. 파일에 그래프의 인접 행렬을 미리 저장해 둔 후, 프로그램을 실행하면 파일에 저장되어있는 그래프의 인접 행렬이 출력 된다. 각 에지에 대한 가중치와 출발점, 도착점은 직접 입력받아 최단경로를 구하게 된다. 인접 행렬의 정의는 다음과 같다.
정점 집합 V(G)={V1 , V2 , ... , Vn}인 그래프 G=(V(G),E(G))의 인접 행렬은 그래프를 구성하는 각 정점들 간의 인접 여부를 n*n의 2차원 배열로 표현한 것이다. 2차원 배열 A(i,j)에서 연결 (Vi , Vj)가 E(G)에 속하면 A(i , j) = 1이 되고, E(G)에 속하지 않으면 A(i,j) = 0 이 된다.

인접 행렬의 문제점은 다음과 같다.
인접 행렬로는 n(n-1)개의 edge를 표현할 수 있다. 그러나 실제로는 그래프내의 edge 수는 이보다 훨씬 적기 때문에 대부분의 행렬 원소는 0의 값을 가진다. 따라서 완전 그래프처럼 edge가 많은 경우를 제외하고는 상당량의 기억 장소가 낭비되는 문제가 있다. 이러한 문제를 해결하기 위해서는 인접 리스트를 사용한다.

<중 략>

▣ 결과 분석 및 토의 (이해나)
첫 번째 읽은 파일의 예를 들어보자. 정점의 개수는 8개, 에지의 개수는 10개이다. 에지(0,1), (0,2), (1,3), (1,4), (2,5), (2,6), (3,7), (4,7), (5,7), (6,7) 의 에지가 있으므로 가중치를 각 에지에 대하여 입력하면 프로그램은 distance배열을 업데이트 시키며 시작점부터 도착점까지의 최단거리를 알려준다.
Dijkstra 최단경로 문제는 두 지점 사이의 가장 짧은 경로를 찾는 문제로서 가중 그래프에서는 구성하는 구간들의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제이다. 예를 들면 지도상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제인데 각 구간에서 걸리는 시간을 가중치에 비유할 수 있으며, 어떤 점 u에서 v로 이동하는 거리도 가중치에 비유할 수 있다. Dijkstra 알고리즘은 인터넷 라우팅에서 사용되는 OSPF(open shortest path first)방식의 프로토콜은 Dijkstra 알고리즘이 실제 현상에서 사용되는 좋은 사례이다.

참고 자료

없음
*하*
판매자 유형Bronze개인인증

주의사항

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

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

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

찾던 자료가 아닌가요?아래 자료들 중 찾던 자료가 있는지 확인해보세요

  • 한글파일 알고리즘_그래프에서 한 정점에서 목적지까지 가는 여러 경로최단 경로구하는 여러 가지 방법에 대해 생각해 보고 이를 정리하시오. 5페이지
    최단거리경로 탐색을 위한 A*와 Dijkstra 알고리즘의 하이브리드 검색법 ... 특정한 목적지까지의 최단 경로구하는 작업을 한다. ... D까지의 최단 경로를 구할 수 있다. 3.
  • 워드파일 진동및메카트로닉스 자율주행 실험 보고서 14페이지
    ) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다 ... 모든 노드에 대한 최단 경로를 파악하는 다익스트라 알고리즘과 다르게 시작 ... 이 알고리즘구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를
  • 한글파일 자료구조 요약정리 7페이지
    -Dijkstra 알고리즘 : 음의 가중치를 허용하지 않는 최단경로 -Bellman-ford ... 경로 알고리즘] -하나의 시작 정점으로부터 각 정점에 이르는 최단 경로를 ... 구한다.
  • 한글파일 최단경로 알고리즘(다익스트라, 플로이드) 12페이지
    기본적 원리로 두어 최단경로를 구해내는 방법이 다익스트라 알고리즘이다. ... 그리디(Greedy) 알고리즘인 다익스트라(Dijkstra) 알고리즘 ? ... 다익스트라(Dijkstra) 알고리즘 (1) 다익스트라 알고리즘이란?
  • 한글파일 Scheduling Problems 동시공학 과제 18페이지
    그 간단한 구현 때문에 많은 사람들이 좋아하는 알고리즘 중 하나이다. ... 거리를 구한다 - 이 최단 거리를 h라고 하자. ... 경로는 원래 그래프에서도 최단 경로가 된다. 2.3 그래프의 변형과 Bellman-Ford
더보기
최근 본 자료더보기
탑툰 이벤트
최단경로를 구하는 Dijkstra의 알고리즘 구현
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
AI 챗봇
2024년 05월 20일 월요일
AI 챗봇
안녕하세요. 해피캠퍼스 AI 챗봇입니다. 무엇이 궁금하신가요?
2:25 오후
New

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