최단경로(shortest path problem)-3

Floyd-warshall algorithm

(all-to-all)

- 가중치 방향 그래프 G=(V,E) , V={1,2,...n}

- 모든 노드 쌍들간의 최단경로의 길이를 구함

- d^k[i,j] 

 : 중간에 노드집합 {1,2,....k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단경로의 길이

경로찾기

경로출력하기