알고리즘(AllPairsShrotest 아래그림(1)은 모든 쌍 최단 경로에 대한 동적 계획알고리즘 수행 그림(2)는 K 3으로 해서 점 3을 경유가능한 점으로 고려해서 모든 쌍에 대한 최단 경로)

소개글

과제 2
아래그림(1)은 모든 쌍 최단 경로에 대한 동적 계획알고리즘 수행하는 과정중 제일 첫 번째 단계로 각점에서 다른 점들까지의 최단 경로의 거리를 나타낸 것이다.
그림(2)는 K=3으로 해서 점 3을 경유가능한 점으로 고려해서 모든 쌍에 대한 최단 경로를 나타낸 그림이다. 다음단계로 점 4를 경유 가능한 점으로 고려해서 모든쌍에 대한 최단 경로를 나타낸 배열 D를 구하는 과정을 자세히 쓰시오(해당 주차 및 교시 : 4강 1차시)
AllPairsShrotest 알고리즘 수행과정

목차

1. 모든 쌍 최단경로 (All-pair Shortest Paths) 알고리즘
2. 과제 내용
3. 풀이
4. 느낀점

본문내용

1. 모든 쌍 최단경로 (All-pair Shortest Paths) 알고리즘하나의 출발점에 대해 모든 정점까지의 최단경로를 구하는 ‘단일 쌍 최단 경로(SSP)’와는 달리, 모든 출발점에 대해 모든 정점까지의 최단경로를 구하는 알고리즘. 모든 쌍 최단경로 알고리즘 중, 가장 잘 알려진 것이 ‘플로이드’ 알고리즘이라고 하며, Floyd-Warshall 알고리즘 이라고 한다.

<중 략>

1. 풀이해당 문제는 Floyd 알고리즘을 통해 배열 D를 갱신해 나가고 있다. 플로이드 알고리즘은 점 {1, 2, ..., k}만들 경우 가능한 점들로 고려하여, 점 i ~ j까지의 모든 경로 중에서 가장 짧은 경로의 거리를 출력한다. 처음에는 1번 점을 경유했을 때의 모든 정점 쌍의 최단거리를 구하고, 그 다음 2번, 3번, ... k번까지 구하게 되면 결국은 모든 정점 - 모든 정점에 최단거리가 작성된 배열 D가 완성된다.

참고 자료

없음