태그 : ShortestPath

단일출발점 최단경로... Dijkstra Shortest Path

 이번에는 특이한 이름만큼이나 유명하신(?) Dijkstra께서 만드신 단일 출발점에서 최단 경로를 구하는 다익스트라 알고리즘이다. 플로이드의 알고리즘과의 차이라면 플로이드의 알고리즘이 각 정점에서 다른 모든 정점으로 가는 최단 경로를 모두 구했다면, 다익스트라 알고리즘은 하나의 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구한다는 것이다.

 그러면 왜 플로이드 알고리즘과 세트로 포스팅 한 것이 아니고, 이렇게 떨어져서 포스팅 하게 되었냐고 한다면, 플로이드 알고리즘은 동적 계획법으로 만들어진 알고리즘이고, 다익스트라 알고리즘은 앞의 두 포스팅인 최소비용 신장 트리처럼 탐욕적인 방법으로 만들어진 알고리즘이기 때문이다.

 알고리즘의 전체적인 구조는 프림의 알고리즘과 거의 차이가 없으므로, 아래의 프림 알고리즘을 알고 있다면 이 알고리즘은 10~20분만에 해결 할 수 있다.
다익스트라 단일 출발점 최단 경로 알고리즘

by sakuragi | 2007/05/09 03:01 | :: R space :: 과제 | 트랙백 | 덧글(7)

최단경로를 구하는 알고리즘... 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 :+: