태그 : Floyd

최단경로를 구하는 알고리즘... Floyd Shortest Path

 아무래도 최근에 가장 많은 시간을 할애하고 있는 것이 이 알고리즘 수업의 과제이다 보니, 자꾸만 포스팅이 이런 내용만 쓰게 된다. 이번의 과제는 알고리즘 자체는 어려운 것이 아니였고, 교수님이 그려주신 그래프를 보고, 플로이드의 최단 경로를 구하는 알고리즘으로 구하는 것이였다.
  옆의 그림이 가중치 방향성 그래프인데, 예를 들면, v3에서 v1으로 가는 가중치(거리/비용)가 -1 이고, v1에서 v3로 직접 가는 방법은 없다는 의미이다. v1에서 v3 로 가기 위해서는 v1 -> v2 -> v3 의 방법①과 v1 -> v2 -> v4 -> v3 의 방법②가 존재하는데 이런 여러 경로 중에서 가중치의 합이 가장 적은 경로를 구하는 것이다. 방법① 경로는 -1 + 2 + 4 = 5가 되고, 방법② 경로는 -1 + 2 + 3 + 7 = 11이 된다. 그러므로 최종적으로 최단 경로는 v1 -> v2 -> v3(방법①)가 된다.

 플로이드 알고리즘은 우선 옆의 그래프를 W 라고 하는 행렬(배열)에 저장한 후에, 플로이드 최단경로 알고리즘(함수)을 실행하면서 최단경로를 D라는 행렬(배열)에다가 점점 최단경로의 값으로 갱신해 나간다(자세한 설명은 "플로이드 알고리즘" 이라고만 검색해도 많이 나오니 참고). 어째든 이번 과제는 이 "최단경로를 구하는 플로이드 알고리즘"이였다.
최단경로를 구하는 플로이드 알고리즘 프로그램

by sakuragi | 2007/04/12 22:28 | :: R space :: 과제 | 트랙백(2) | 덧글(16)

◀ 이전 페이지          다음 페이지 ▶

:+: sakuragi's Steam :+: