*세* 스토어

*세*

개인

팔로워0 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

1개
전체 판매량

1개
최근 3개월 판매량

0개
자료후기 점수

-
자료문의 응답률

-

전체자료 1개

알고리즘설계

플로이드 알고리즘은 그래프 상의 모든 노드와 모든 노드 사이의 최단거리를 구하는 알고리즘입니다. 시간복잡도가 O(N^2)인 dijkstra알고리즘을 모든 쌍에 대해서 구하는 방법 (O(N^3)이 되겠죠..)과 같은 O(N^3)의 시간복잡도를 가진 알고리즘입니다. 하지만 대부분의 경우 플로이드 알고리즘이 그 과정이 단순하기 때문에 훨씬 빠른 속도로 동작 합니다.더욱이 이 알고리즘이 더 매력적인 것은 알고리즘의 구현이 매우 간단하다는 것입니다.for k := 1 to n dofor i := 1 to n dofor j := 1 to n doif e[i, j] > e[i, k] + e[k, j] thene[i, j] := e[i, k] + e[k, j];실제로 모든 쌍의 최단거리를 찾는 부분은 위의 5줄에 불과합니다. 아래 소스의 나머지 부분은 최단거리의 '경로'를 찾는 과정입니다.알고리즘에 대해서 약간 설명을 하자면 i, j간에 기존에 알려진 최단거리 e[i, j]와 노드 k를 거치는 최단거리 e[i, k] + e[k, j]를 먼저 비교합니다. 노드 k를 경유하는 것이 원래의 최단거리보다 짧다면 최단거리를 갱신해 줍니다. 원래 이렇게 간단하지만은 않지만 자세한 것은 참고 서적을 찾아보시면 됩니다. 아, 그리고 for문의 순서가 틀리면 제대로 동작하지 않을 수 있으니 유의하시기 바랍니다.보통의 경우 가중그래프는 노드 u와 v간에 에지가 없음을 표현할 때 e[u,v]에 0을 기록해 주는 것에 반해 이 Floyd알고리즘은 약간 다른 표기법을 필요로 합니다.u, v간에 에지가 없으면 : u = v일 때 0: u v일 때 무한대(∞)u, v간에 에지가 있으면 : 에지의 가중치문제는 컴퓨터로는 무한대를 표현할 수 있는 방법이 없다는 것입니다. 이럴 때에는 적당히 큰 값을 써주면 됩니다. 하지만 너무 큰 값을 넣을 경우 e[i, k] + e[k, j]를 계산하는 과정에서 overflow 에러가 발생할 수 있습니다. 또한 너무 작으면 최단거리를 구하는 과정이 제대로 동작하지 않게 되겠죠.하드에 쳐박혀 있는 소스를 올려 보겠습니다. 제대로 테스트 해 본 것은 아니지만 아마 잘 돌아 갈겁니다. (-_- 지금 학교라서..) 최단거리의 "경로"(어느 어느 노드를 거치는지)를 찾는 것은 잘 연구해 보시기 바랍니다.program FloydAlgorithm;constnoedge = 10000;varn : integer;e, p : array[1..100, 1..100] of integer;procedure input_file;varf : text;i, j : integer;beginassign (f, 'graph.txt');reset (f);readln (f, n);for i := 1 to n do beginfor j := 1 to n do beginread (f, e[i, j]);if i = j then begine[i, j] := 0;p[i, j] := 0;end else beginif e[i, j] = 0 then begine[i, j] := noedge;end else beginp[i, j] := i;end;end;end;end;close (f);end;procedure floyd;vari, j, k, l : integer;path : array[1..100] of integer;beginfor k := 1 to n do beginfor i := 1 to n do beginfor j := 1 to n do beginif e[i, j] > e[i, k] + e[k, j] then begin

자연과학| 2001.04.03| 4페이지| 1,000원| 조회(1,004)

알고리즘, 플로이드, 프로그램소스, 시간복잡도

미리보기

닫기