# 플로이드 와샬 알고리즘

삼중 for문으로 모든 정점을 순회하면서\
"나 거쳐서 갈 수 있는 놈들 있어? 싹 다 갱신해봐"

가 플로이드 와샬 알고리즘이다.

### 이행적 폐쇄 (Transitive Closure)

비용 상관없이 갈 수 있느냐 없느냐만 따져보면

```python
for k in range(n):  # 나 A를 거쳐서
    for i in range(n):  # B 너가
        for j in range(n):  # C로 갈 수 있니?
            if closure[i][k] and closure[k][j]:
                closure[i][j] = True
```

첫번째 for문 요소 : "나 A를 거쳐서"\
두번째 for문 요소 : "B 너가"\
세번째 for문 요소 : "C로 갈 수 있니?"

"나 A를 거쳐서, B 너가, C로 갈 수 있니?"

### 최소 비용 (Floyd-Warshall Algorithm)

최소 비용 버전으로 보면

```python
for k in range(n):  # 나 A를 거쳐서 가는게
    for i in range(n):  # B 너가
        for j in range(n):  # C로 갈 때 더 빨리 가니?
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
```

첫번째 for문 요소 : "나 A를 거쳐서 가는게"\
두번째 for문 요소 : "B 너가"\
세번째 for문 요소 : "C로 갈 때 더 빨리 가니?"

"나 A를 거쳐서 가는게, B 너가, C로 갈 때 더 빨리 가니?"


---

# Agent Instructions: 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://lazyartisan.gitbook.io/note/main-page/algorithm/undefined/undefined-3.md?ask=<question>
```

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.