최단경로 탐색

소개글

완벽한 소스 프로그램입니다

목차

▣ 문제개요

▣ 문제 분석 및 해결방법

▣ 소스코드 및 주석

▣ 실행화면

▣ 느낀점

본문내용

▣ 문제개요
한 정점에서 다른 한 정점으로 까지의 최단경로를 탐색하고 나타내어라. 정점의 개수와 각 정점 사이의 거리는 사용자로부터 직접 입력받도록 한다.


▣ 문제 분석 및 해결방법
S를 최단경로가 발견된 정점의 집합(정점 v포함)이라 하면, S에 속하지 않는 w에 대해 dist[w]를 v에서 시작하여 S에 있는 정점만을 거쳐 w까지 가는 최단경로의 길이라 정의한다면
⓵ 만일 다음으로 짧은 최단경로가 정점u까지의 경오라면 v에서 u로의 경로는 오직 S에 속한 정점들만을 통하게 된다. 이것을 증명하기 위해서는 u로의 최단경로 상에 있는 중간 정점들이 모두 이미S에 포함되고 있음을 보여야 한다. 만일 S에 속하지 않는 정점 w가 이 경로상에 있다면 v에서 u로의 경로는 이 길이보다 짧은 v에서 w까지의 경로를 포함해야 한다. 최단경로들은 경로 길이의 비감소순으로 구해지나고 가정하므로, v에서 w까지의 최단 경로는 이미 구해 졌어야 한다. 그러므로 S에 속하지 않는 중간 정점이란 있을수 없다,
⓶ 다음에 생성되는 경로의 종점은 S에 없는 정점들 중에서 최단거리 dist[u]를 가진 정점 u가 되어야 한다. 이는 dist의 정의와 전술한 ⓵로부터 알 수 있다. S에 속하지 않느면서 거리가 같은 정점들이 여러개 있을 경우 임의의 하나의 정점을 선택할수 있다.
⓷ 일단 ⓶에서 선택된 정점 u는 S의 원소가 된다. v에서 u로의 최단경로는 ⓶의 선택과정을 통해 이루어 진다. 이때 v에서 시작하여 S에 있는 정점만을 통해 현재 S에 속하지 않은 w까지의 최단경로의 길이는 감소될수 있다. 즉 dist[w]의 값이 변경될수 있다. 거리가 바뀌는 때는 v에서 u까지 또한 u에서 w까지의 경로상에 있는 중간 정점들은 모두 S에 포한되어 있어야 한다.

참고 자료

없음