Dijkstra 알고리즘을 ST에 적용

소개글

딕스트리 알고리즘 해석입니다.

목차

1.스페닝 트리의 개념 1
2.스페닝 트리 사용 1
3.최소비용 스페닝 트리 2
4. 구현 방법 2
5. 딕스트라 (dijstra) 적용한 ST를 찾을 때 예제 2
6. 최단 경로를 구하는 과정 6
7. 참고문헌 6

본문내용

1. 스페닝 트리의 개념
- 스페닝 트리(Spanning Tree)는 “신장 트리” 이라고 한다.
- 원래 그래프에서 장점은 그대로이고 간선은 노드의 수보다 1개 적으며 원래 그래프
를 연결된 상태로 만드는 그래프를 말한다.
- 간선의 수가 장점의 수보다 1개 적으므로 그래프에 사이클이 없게 한다.

2. 스페닝 트리 사용
첫째: 경기도 10개 도시의 송유관을 건설한다고 할 때 어떻게 하면 중복시키지 않고(사이클이 없이) 9개 송유관으로 모든 도시를 원류 공급지와 연결을 시킬 것인가? 하는 문제는 그래프에서 스페닝 트리 문제가 된다.

둘째: 건물간의 컴퓨터 네트웍을 연결할 때 사이클이 없이 전체 건물이 연결되도록 통신선을 구성할 것인가가 스페닝 트리 문제가 된다.

3. 최소비용 스페닝 트리(MST: Minimun Cost Spanning Tree)
- 신장트리 중에서 사용된 간선들이 가중치 합이 최소인 트리

ex)
- 도로건설: 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
- 전기회로: 단자들을 모두 연결하면서 전선의 길이가 최소가 되도록 하는 문제
- 통신: 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제

4. 구현 방법
1) Kruscal 방법
- 간선중 비용이 작은 것부터 큰 순으로 소트(5,6,10,11....)
- 가장 작은 비용이 드는 간선부터 차례로 추가(5,6,10....)
- 추가 중 사이클이 존재하는 간선은 제외
- 모든 장점이 연결될 때까지 반복

2) Prim 방법
- 임의의 장점을 선택
- 이 장점에서 다른 장점으로 갈수 있는 최소 비용의 장점을 선택
이 장점은 제외
- 이 장점에서 다른 장점으로 가는 비용과 기존과 비교 후 더 작은 비용이
있으면 갱신
- 2-3번 과정을 n(장점의 수) -1번 반복

참고 자료

[1] TCP/IP Protocol Suit3 3e 김병철 외 공역
[2] 2007년 1학기 2학년 자료구조 그룹발표 6조 참조
[3] 네이버 지식 검색
[4] C언어 쉽게 풀어 쓴 자료구조/ 생능출판사
[5]http://cafe.naver.com/missilewarfare.cafe?iframe_url=/ArticleRead.nhn%3Farticeid=2939