플로이드-워셜

플로이드-워셜 floyd-warshall

 

그래프에서 최단 거리를 구하는 알고리즘

모든 노드 간에 최단 경로 탐색

음수 가중치 에지가 있어도 수행 가능

동적 계획법의 원리를 이용해 알고리즘에 접근

D[s][e] = min(D[s][e], D[s][k] + D[k][e])

---

1. 리스트 선언하고 초기화하기

s == e 인 경우, 0

s != e 인 경우, 무한

2. 최단거리 리스트에 그래프 데이터 저장

3. 점화식으로 리스트 업데이트하기 (n: 노드 개수)

for 경유지 k에 대해(1, n):

    for 출발노드 s에 대해(1, n):

        for 도착노드 e에 대해(1, n):

            D[s][e] = min(D[s][e], D[s][k] + D[k][e])