검색어 입력폼

최단경로 알고리즘(다익스트라, 플로이드)

저작시기 2009.12 |등록일 2010.02.24 한글파일한글 (hwp) | 12페이지 | 가격 2,200원

소개글

최단경로 알고리즘(다익스트라, 플로이드)

목차

1. 최단경로란?

2. 다익스트라(Dijkstra) 알고리즘
(1) 다익스트라 알고리즘이란?
(2) 다익스트라 알고리즘의 원리
(3) 다익스트라 알고리즘의 구체적 적용
(4) 다익스트라 알고리즘의 구현을 위한 소스코드 및 출력결과

3. 플로이드(Floyd) 알고리즘
(1) 플로이드 알고리즘이란?
(2) 플로이드 알고리즘의 원리
(3) 플로이드 알고리즘의 구체적 적용
(4) 플로이드 알고리즘의 구현을 위한 소스코드 및 출력결과

4. 다익스트라 알고리즘과 플로이드 알고리즘의 비교

본문내용

1. 최단경로란?
(1) 최단 경로 : 두 정점을 연결하는 간선들의 가중치의 합이 최소인 경로를 말한다.
(2) 최단 경로 문제 : 한 가중치 그래프에서 주어진 두 정점 x와 y를 연결하는 경로 상의 모든 선분들의 가중치 합이 최소인 성질을 갖는 경로를 찾는 것이다.
(3) 최단 경로 기법 :
➀ 그리디(Greedy) 알고리즘인 다익스트라(Dijkstra) 알고리즘
➁ 동적계획법(Dynamic Programming)인 플로이드(Floyd) 알고리즘
(4) 최단경로가 사용되는 예 :
➀ GPS를 이용한 네비게이션 시스템
➁ 지하철 노선도 최단경로 검색 시스템
➂ 수송 시스템

2. 다익스트라(Dijkstra) 알고리즘
(1) 다익스트라 알고리즘이란?
- 그리디 알고리즘은 전후 상황을 파악하지 않고, 현재 시점에서 가장 최적의 상황을 찾아 경로를 파악해 나가는 것이다. 즉 최적 해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하게 된다.
- 그리디 알고리즘을 기본적 원리로 두어 최단경로를 구해내는 방법이 다익스트라 알고리즘이다. 여기서 다익스트라는 만든 사람의 이름을 딴 것이다.

(2) 다익스트라 알고리즘의 원리
- 다익스트라 알고리즘을 구체적으로 적용하기 전에 해결과정을 정리해 보면 다음과 같다.
① 가중치인접행렬에서는 직접 연결된 것이 없으면 무한대, 연결된 간선은 가중치를 표현한다.
② 두개의 집합 S와 C를 만들어 S에는 출발점을 초기값으로, C는 출발점을 제외한 모든 정점을 초기값으로 한다.
③ S에서 정해진 초기값으로부터 C의 각 정점에 대한 최단 경로 dist[i]를 구한다.
④ dist[i]의 기록 중에서 최단 경로를 택하여 해당 정점 v를 C에서 제거 후 S에 넣는다.
⑤ S의 초기 정점과 C에 직접 이르는 거리와 S안의 모든 정점을 거친 후 C에 이르는 거리중 최단 경로를 dist[w]로 한다.
⑥ ➃-➄의 과정을 C가 공집합이 될 때까지 반복한다.

참고 자료

없음
다운로드 맨위로