> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/undefined-4/undefined-3.md). # 플로이드 와샬 * 다익스트라 : 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 * 플로이드 와샬 : '거쳐가는 정점을 기준'으로 최단거리를 구하는 알고리즘\ \=> '**모든 정점**'에서 **'모든 정점**'으로의 최단 경로를 구하고 싶을 때.\ \=>마찬가지로 다이나믹 프로그래밍 기술에 의거 ![](/files/-MiKdaL1x133bww_BDDU) 각각의 정점이 다른 정점으로 가는 비용 | 0 | 5 | ∞ | 8 | | - | - | - | - | | 7 | 0 | 9 | ∞ | | 2 | ∞ | 0 | 4 | | ∞ | ∞ | 3 | 0 | 이제 이 테이블이 의미하는 바는 '현재까지 계산된 최소 비용'이다. 이러한 이차원 배열을 반복적으로 갱신하여 **최종적으로 모든 최소 비용**을 구해야 한다. 바로 그러한 **반복의 기준**이 '**거쳐가는 정점**' 이 된다! 1. **노드1을 거쳐가는 경우** | 0 | 5 | | 8 | | - | - | - | - | | 7 | 0 | 9 | | | 2 | | 0 | | | ∞ | | | 0 | 노드 1을 거쳐가는 경우는 위와 같이 6가지 공간만을 갱신주면 된다. 이 때 바로 다음 두식을 비교해주는 방식을 반복한다!\ \=> 노드 1을 제외한 노드 2,3,4 가 있을 때, 각 노드 <=> 1을 제외한 경로들에 대해 최솟값 비교 & 최단거리 값 갱신한다! 자기 자신으로 가는 경로가 없을 경우 이 경우도 제외.\ 1->3\ 2->4\ 3->2, 3->4\ 4->2, 4->3 X->Y 최소 비용 vs **X->노드1로 가는 비용** + **노드1 ->Y로 가는 비용**\ **즉, 1을 거쳐서 가는 경우가 더 빠른 경우가 존재한다면 빠른 경우로 최소 비용을 계산한다. 예를 들어 D\[2,3]은 D\[2,3] 과 D\[2,1] + D\[1,3] 중에서 더 작은 값으로 교체된다. 따라서 노드1을 거쳐가는 경우 계산하면 다음 표와 같이 구성된다.** | **0** | 5 | ∞ | 8 | | ----- | - | - | -- | | 7 | 0 | 9 | 15 | | 2 | 7 | 0 | 4 | | ∞ | ∞ | 3 | 0 | 2\. 노드 2를 거치는 경우\ \=> 마찬가지로 2를 제외한 나머지 모드 1,3,4에 대해 2<=>1,3,4 를 제외하고 구하면 된다.\ 남겨두는 것. 이용하기 위해.\ 1->1,1->2\ 2->1,2->2,2->3,2->4\ 3->2,3->3\ 4->2,4->4\ 구해야하는 것 총 6개!\ 1->3,1->4\ 3->1,3->4\ 4->1,4->3 | 0 | 5 | | | | - | - | - | -- | | 7 | 0 | 9 | 15 | | | 7 | 0 | | | | ∞ | | 0 | D\[1]\[3] vs (D\[1]\[2] + D\[2]\[3]) = ∞ vs (5+9) = 14\ D\[1]\[4] vs (D\[1]\[2] + D\[2]\[4]) = 8 vs (5+4) = 8\ D\[3]\[1] vs (D\[3]\[2] + D\[2]\[1]) = 2 vs ( 7+7) = 2\ D\[3]\[4] vs (D\[3]\[2] + D\[2]\[4]) = 4 vs (7+15) = 4\ D\[4]\[1] vs (D\[4]\[2] + D\[2]\[1]) = ∞ vs (∞+7) = ∞\ D\[4]\[3] vs (D\[4]\[2] + D\[2]\[3]) = 3 vs (∞+9) = 3 | 0 | 5 | 14 | 8 | | - | - | -- | -- | | 7 | 0 | 9 | 15 | | 2 | 7 | 0 | 4 | | ∞ | ∞ | 3 | 0 | 이런 식으로 노드 X에서 출발, 노드 Y에 도착할 때 ①원래 경우와 ②경유지 K를 거쳐서 가는 경우를 비교해서 더 작은 값으로 갱신시켜 모든 정점 -> 모든 정점 최단거리를 구한다! ① 원래 경우 : D\[X]\[Y]\ ② 경유지 K를 거쳐서 가는 경우 : D\[X]\[K] + D\[K]\[Y]\ ③ D\[X]\[Y] = Math.min(D\[X]\[Y],D\[X]\[K] + D\[K]\[Y]) --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/undefined-4/undefined-3.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.