최단경로

소개글

1. 문제 인식
사용자로부터 그래프를 입력받아 최단경로를 찾아 출력하는 dijkstra알고리즘을 짜시오.

2. 문제 접근 방법 및 분석
① Dot 클래스의 정의
세가지 변수를 정의하는데 각 정점간의 거리와 최단경로를 찾았을때 ture, 못찾았을때 false를 나타내기 위해 bool형을 이용하였으며 최종 최단거리를 기억하는 변수도 설정하였습니다.

목차

1. 문제 인식

2. 문제 접근 방법 및 분석

3. 소스코드 및 주석

4. 결과화면(교과서에 나온 그래프 입력)

5. 느낀점

본문내용

① Dot 클래스의 정의
세가지 변수를 정의하는데 각 정점간의 거리와 최단경로를 찾았을때 ture, 못찾았을때 false를 나타내기 위해 bool형을 이용하였으며 최종 최단거리를 기억하는 변수도 설정하였습니다.

②shortt 클래스의 정의
short클래스에서 이중배열을 만들어 입력을 받고 출력을 하고 최단 최소거리를 찾는 모든 역할을 하도록 하였습니다.

③거리 입력
우선 사용자로부터 정점의 개수를 입력받고 각각의 정점의 거리들을 하나하나 입력받습니다.
여기서 갈수 없는 길일 경우 100000(십만)을 입력하도록 하였습니다. 십만일 경우 출력시 갈수 없는 길임을 출력하도록 하였습니다, 십만일 경우 어떤 경우의 수보다 작기에 최단거리로 선택될 수가 없습니다.

④최소 비용 계산
우선 하나의 간선으로 갈수 있는 최단경로를 설정합니다. 갈수 없는 정점으로는 십만을 입력했기에 우선 십만이 최단경로가 됩니다. 두 번째로 두 개의 간선으로 갈수 있는 최단경로를 선택합니다. 그 후 하나의 간선으로 갈수 있는 최단경로와 두 개의 간선으로 갈수 있는 최단경로중 더 적은 최단 경로를 선택하여 배열에 저장합니다.

⑤최단 경로 선택
지금까지 결정되지 않는 경로를 선택하여 비교를 하여 선택되지 않는 경로 중에서 가장 짧은 것을 찾습니다.

참고 자료

없음