[조선해양공학]동적 계획법_플로이드 알고리즘

소개

동적계획법(Dynamic Programming)
- 플로이드 알고리즘(Floyd Algorithm) -
[조선해양공학과]모든 노드에서 자신을 제외한 다른 모든 노드로 가는 최단거리 경로를 얻을 수 있는 플로이드 알고리즘의 동적 계획법의 분석 레포트입니다.

목차

1.개 요
2.플로이드 알고리즘에 사용된 자료구조
3.플로이드 알고리즘의 문제 해결 방법
4.예 시
5.방 법
6.플로이드 알고리즘의 의사코드
7.플로이드 알고리즘의 의사코드(최단거리 경로 추가)
8.최단경로 출력

본문내용

동적계획법(Dynamic Programming)
- 플로이드 알고리즘(Floyd Algorithm) -

■ 개 요
플로이드 알고리즘은 최단거리 경로를 구하는 또 다른 방식의 알고리즘이다. 전에 배운 다익스트라의 최단거리 알고리즘은 그리디 알고리즘을 이용한데 반해, 플로이드의 최단거리 알고리즘은 동적계획법을 이용한다. 이 알고리즘을 사용하면 모든 노드에서 자신을 제외한 다른 모든 노드로 가는 최단거리 경로를 얻을 수 있다.

■ 플로이드 알고리즘에 사용된 자료구조
∙배열 w[i][j] : 가중치포함 방향그래프를 배열 w로 표현한다. 이 배열의 구성방법은 다익스트라의 <이미지 포함> 최단거리 알고리즘에 사용한 그래프 배열과 같다.
∙배열 d[i][j] : 집합 {v1, v2, . . . , vk}에 속하는 정점만을 중간 정점으로 사용하면서 vi에서 vj로 가는 최단경로 길이 <이미지 포함>
다음과 같은 가중치포함 방향그래프가 있다고 가정해보자.
배열 w는 위 그래프를 나타내고, 배열 d는 최단경로의 길이를 가지고 있다. 최단경로를 푸는 알고리즘은 w에 있는 값을 가지고 d에 있는 값을 계산한다.
■ 플로이드 알고리즘의 문제 해결 방법
다음 예시를 보고 개략적인 방법에 대해 이해해보자.
<이미지 포함>
▲ 예 시
위 그래프를 가지고 v2에서 v5로 가는 최단거리 경로를 구해보자.

참고자료

· 없음