728x90 반응형 플로이드와샬1 플로이드 와샬(Floyd Warshall) 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘을 사용한다. "거쳐가는 정점을 기준으로 최단 거리를 구하는 것" 위의 그래프에서 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열에 출력하면 이 테이블이 의미하는 것은 현재까지 계산된 최소 비용이다. 이러한 이차원 배열을 반복적으로 갱신하여 최종적으로 모든 최소 비용을 구해야 한다. 반복의 기준이 '거쳐가는 정점' 인 것이다. 노드 1을 거쳐가는 경우 노드 1을 거쳐가는 경우는 위와 같이 6가지 공간만 갱신해준다. 즉, 예를 들어 2에서 3으로 가는 경우에는 2에서 3으로 가는 경우의 비용과 (2에서 1로 가는 경우) + (1에서 3으로 가는 경우)의 비용을 더한 값을 비교한다. 더 작은 값으로 교체한다. 2. 노드 2를.. 2019. 4. 26. 이전 1 다음 728x90 반응형
