플로이드 워셜 알고리즘

다익스트라 알고리즘은 시작점 고정 → 모든 노드로 가는 최단 경로를 테이블로 관리한다.

그렇게 때문에 1차원 테이블이 필요하다

A → A	A→B	A→C	A→D

플로이드-워셜 알고리즘은 모든 출발점에서 모든 도착점으로 가는 최단경로를 찾기 때문에

2차원 테이블이 필요하다.

출발 - 도착	A	B	C	D
A	0
B		0
C			0
D				0

자신 → 자신으로 가는 경우에는 0
직행 노선이 없는 경우는 “무한”으로 표시한다.

💡 점화식

과정

1. 무한대로 초기화한 2차원 list만들기
2. 자신 → 자신 = 0 으로 초기화
3. 간선 입력받고, 그 간선 값 초기화
4. 점화식을 이용해서 A→ B 값을 K 를 거쳐 가는 곳과 비교해서 값 업데이트
   1. 3중 for 문이 필요하다
   2. K → A → B