[유니와이즈 이산수학]과제점수 만점, 주어진 그래프에서 최단경로 구하기

소개

"[유니와이즈 이산수학]과제점수 만점, 주어진 그래프에서 최단경로 구하기"에 대한 내용입니다.

목차

Ⅰ. 서론

Ⅱ. 본론
ⅰ. a에서 f까지 가능한 경로와 거리를 구하기
ⅱ. 다익스트라 알고리즘을 이용한 최단경로 구하기

Ⅲ. 결론

Ⅳ. 참고문헌

본문내용

Ⅰ. 서 론
그래프 이론은 현재 활발하게 연구되는 수학 분야로서, 유전학, 사회학, 화학, 통신 및 정보 분야, 생태학, 교통문제 해결 등 다양한 곳에 활용된다. 특히 최단 경로 문제는 물류, 통신, 네비게이션 등 실생활에 밀접하게 활용된다. 이러한 최단 경로 문제를 해결하는 대표적인 방법 중 하나가 다익스트라(Dijkstra) 알고리즘이다.
본 과제에서는 주어진 방향 그래프에서 시작점 a에서 도착점 f까지 도달할 수 있는 모든 경로와 그 거리를 구하고, 다익스트라 알고리즘을 적용하여 최단 경로를 계산하는 과정을 단계별로 상세히 기술하고자 한다.

Ⅱ. 본 론
ⅰ. a에서 f까지 가능한 경로와 그 거리를 구하기.
정점 a에서 f까지 도달 가능한 주요 경로와 그 거리는 다음과 같다.

<중 략>

ⅱ. 다익스트라 알고리즘을 이용한 a에서 최단경로 구하기
출발 정점에서 시작하여 현재의 정점까지의 값과 인접한 정점의 가중치 합이 가장 작은 정점을 다음 정점으로 선택하고 그 경로를 최단 경로에 포함시킨다. 이 과정을 모든 정점이 선택될 때까지 반복한다.

참고자료

· 네이버 지식백과 https://terms.naver.com/entry.naver?docId=842526&cid=50371&categoryId=50371
· https://terms.naver.com/entry.naver?docId=3404983&cid=47324&categoryId=47324
· 유니와이즈원격평생교육원 이산수학 교안