Dijkstra 알고리즘을 이용한 지하철 망 탐색 문제(C++, 그래프, 인접리스트)

등록일 2002.11.20 압축파일 (zip) | 1페이지 | 가격 1,400원

소개글

Debug - VC++ 6.0 으로 컴파일된 디버그 폴더
___425 assn4_testcase1.txt - 테스트용 예제
___504 assn4_testcase2.txt
___639 assn4_testcase3.txt
___989 assn4_testcase4.txt
___979 assn4_testcase5.txt
_2,159 assn4_testcase6.txt
_1,303 Dijkstra.plg
23,040 Assignment4.doc - 과제 문서
_4,306 Dijkstra.dsp
___541 Dijkstra.dsw - VC++ 6.0 용 워크스페이스 파일
50,176 Dijkstra.ncb
10,354 SubWay.cpp - 메인 소스
53,760 Dijkstra.opt
로 구성되어 있습니다.

알고리즘 과제물로 제작된 '지하철 역 최소 경로 탐색 문제' 입니다.
VC++ 6.0 으로 제작되었으며 예제파일 6개가 포함되어 있습니다.
그래프를 인접 리스트로 표현하도록 되어 있으며 전체 그래프를 도착 역을 루트로 만들어 최소비용 신장 트리를 구성합니다.

** 주석이 대화체로 매우 상세하게 적혀 있습니다 **

똑같은 문제가 아니더라도 Dijkstra 경로탐색 알고리즘은 유용하게 사용하실 수 있을겁니다.

Assignment4.doc 는 교수님께서 공개하신 숙제 출제용 문서입니다.

목차

없음

본문내용

지하철 망이 주어져 있다. 다음을 해결하는 프로그램을 작성하시오.

(1) 지하철 망이 연결되어(connected) 있는지, 즉 모든 두 역 사이의 경로가 있는지를 판별하시오.
(2) 지하철 망에 사이클이 있는지를 판별하시오.
(3) 지하철 망의 두 역 사이의 가장 시간이 적게 걸리는 경로와 그 시간을 출력하는 프로그램을 작성하시오.

참고 자료

Dijkstra 알고리즘과 최소비용 신장 트리 알고리즘
*원하는 자료를 검색 해 보세요.
  • BFS + DFS 인접리스트와 인접행렬로 구현 0페이지
    1. 인접행렬 표현 그래프에 대한 DFS 순회2. 인접 리스트 표현그래프에 BFS 순회3. 인접행렬 표현 그래프에 대한 BFS 순회4. 인접리스트 표현 그래프에 대한 DFS 순회[제약 사항]1) 입력 예제 그래프는 임의로 준비하되, 정점의 개수는 10개이상간선의 갯수는..
  • [자료구조] 링크드 리스트(Linked List) 정렬 레포트 10페이지
    <자료구조 및 실습 Report> Linked List의 정렬 학 과 : 컴퓨터공학과 학 년 : 2학년 학 번 : 성 명 : Linked List의 정렬 □ 문제분석 입력자료를 스트링으로 받아들여 그것을 링크드리스트로 만든다음 그 자료를 사용하여 정렬시킨다. □ 알고리..
  • DFS(깊이우선탐색), BFS(너비우선탐색) 0페이지
    C++로 작성한 DFS와 BFS입니다..h 파일과 .cpp 파일로 나눠져 있으며, 각 줄마다 주석 첨부되어있습니다.실행시에 우선 각 vertex에 대한 인접리스트가 출력(안내)되고 사용자가 임의로 startVertex를 입력해주면 그 시작점에 대한 DFS와 BFS가 출..
  • [프로그래밍] 자료구조 6페이지
    구성 1) 인접리스트 생성 우선 인접리스트를 작성하기위한 알고리즘을 구현한다. void MakeList(int weight) 이 함수를 호출함으로써 아래와 같이 인접리스트가 생성된다. 2) DFS 알고리즘을 구현하여 scan한다 프로그램 #include..
  • [자료구조] 인접 리스트(Adjacency List)를 이용한 그래프(Graph)의 구현 0페이지
    ㅁ 주 제 : 인접 리스트(Adjacency List)를 이용한 그래프(Graph)의 구현ㅁ 내 용 : 설명(리포트) + 소스코드그래프(Graph) 및 인접리스트(Adjacency List)에 대한 이론적인 내용정리 뿐만 아니라,작성된 소스코드에서 사용된 각각의 함수..
  • 자료구조 - 그래프의 표현 12페이지
    그래프의 표현 그래프 표현의 개념 그래프는 수행하는 기능 이나 응용 방법 에 따라 다양한 방법을 이용하여 메모리 내에 표현할 수 있는데 , 대표적으로 3 가지 방법 이 있다 . * 인접 행렬 (Adjacency Matrix) * 인접 리스트 (Adjacency List..
  • 알고리즘 5페이지
    <가중그래프에서 두 점 사이의 최단 거리를 구하는 방법> Ⅰ. 그래프 G = (V, E) · V : 정접의 집합 · E : 간선의 집합 · 2차원 배열을 이용하여 인접 행렬이나 연결리스트 형태의 인접리스트로 표현 가능 Ⅱ. 인접행렬 · A=(n*n)의 임의의 원소 A..
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      Dijkstra 알고리즘을 이용한 지하철 망 탐색 문제(C++, 그래프, 인접리스트)