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