[공학]최단경로 탐색을 위한 Dijkstra Tree Algorithm

소개글

최단경로 탐색을 위한 Dijkstra Tree Algorithm을 알아보고 이를 C 프로그램을 통하여 구현한 레포트입니다.

목차

1. 서론

1.1 개요
1.2 경로선택 알고리즘 개요
1.3 수형망(tree building)과 넝쿨망(vine building)의 비교

2. 본론

2.1 Dijkstra Algorithm 의 특징
2.2 Dijkstra Algorithm의 진행과정
2.3 Dijkstra Tree Algorithm 을 이용한 예제

3. 프로그램에 의한 검증

4. 결론


참고문헌

본문내용

1. 서론

1.1 개요
교통모형 기법에 이용되는 최단경로 탐색 알고리즘은 각 노드로의 누적시간과 전 노드를 개선하는 하나의 고유한 방법으로 도출 되었다. 이들의 차이는 개선과정에 있어서 자료구조를 어떻게 변화시키는가에 따라 정의될 수 있다.
최단경로 문제는 1950년대 Ford(1956)와 Bellman(1975)의 알고리즘을 기반으로 하여 Moore(1975)와 Dijkstra(1957)의 의해 그 기틀이 다져졌으며, 그 이후 많은 알고리즘들이 제안되어 왔다.

2. 본론

2.1 Dijkstra Algorithm 의 특징
▪ Dijkstra Algorithm 은 Label - setting 기법을 적용한 알고리즘으로 이해가 쉽고 각종 최단경로 문제에 광범위하게 적용될 수 있으며, 사용이 간편함으로써 가장 널리 사용되는 알고리즘이다.
▪ Dijkstra Algorithm 은 기점에서부터 여러 개의 대안 경로가 있을 경우 최적의 원리에 근거로 하여 최소비용 경로를 찾아 해당노드를 영구표지로 선정하는 단계를 거치므로 계산과정이 짧은 장점이 있으나, 다른 우회경로에 대한 고려를 할 수 없는 단점이 있다.
▪ 모든 링크의 weight가 nonnegative한 값을 갖는다는 것이 기본 가정이다.즉, 이 성립한다. 경로를 이루는 링크의 수가 늘어날수록 경로의 길이도 증가한다는 의미이다.

2.2 Dijkstra Algorithm의 진행과정
▪ 기본 Parameter


▪ setp 1 : 초기화
- Network상 모든 node 에 대하여 로 설정하며, 로 초기화
- Loose-Ends Table의 출발노드 h 와 연결되는 모든 도착노드 j 를 넣음
- h 를 NEXT 로 설정

참고 자료

▪ YOSEF SHEFFI - URBAN TRANSPORTATION NETWORK
: Equilibrium Analysis with Mathematical Programming Methods (1985)
▪ ROY THOMAS - Traffic Assignment Techniques (1933)
▪ Ravindra K.Ahuja, Thomas l.Magnanti, James B.Orlin - NETWORK FLOWS (1993)
▪ Pape, U. - Implementation and Efficiency of Moore
- Algorithms for the Shortest Path Problem (1974)
▪ 배영승 - C++ 들어서기 1권, 2권 (2001)
▪ 김명환 - 비주얼 C++ 입문 (2000)