알고리즘_워셜 알고리즘_최단경로

소개글

워셜알고리즘으로 최단경로 분석과 선정이유부터 결론까지 작성되어있습니다.

목차

Chapter 1. 과제정의
1-1. 과제의 간략한 설명
1-2. 사용 알고리즘
(1) 버블정렬(Bubble Sort)
(2) 선택정렬(Selection Sort)
(3) 삽입정렬(Insertion Sort)
(4) 퀵정렬(Quick Sort)
(5) 합병정렬(Merge Sort)

Chapter 2. 분석
2-1. 출력화면
2-2. 결과정리
(1) 표
(2) 그래프

Chapter 3.결론

본문내용

Chapter 1. 시스템정의
1-1. 과제의 간략한 설명
Cost가 다른 두 개의 connected graph A와 B의 최단거리를 알아보는 과제로, 출발지 S와 목적지 T는 모두 Graph B에 있다는 조건을 갖는다.

1-2. 사용 알고리즘(The Floyd-Warshall Algorithm)
(1) The Floyd-Warshall Algorithm 선택이유
Dijkstra Algorithm은 한 정점에 대해 다른 모든 정점에 대한 최단거리를 구하게 되고 Floyd-Warshall Algorithm은 모든 정점간의 최단거리를 구하기 때문에 모든 정점간의 거리를 구하는 all-to-all 방식을 이용하기 위해서 Floyd Algorithm을 선택했다.

(2) The Floyd-Warshall Algorithm 설명
0부터 k까지의 정점만을 사용해서 정점(v) i에서 정점(v) j로 가는 최단 경로는 2가지의 경우로 나뉘어진다.
• 정점 k를 거쳐서 가지 않는 경우
- 정점 i에서 j로 가는 경우 최단 거리는 당연히 A[i][j]가 된다.

참고 자료

없음