최단경로 Moore Tree 알고리즘

소개글

최단경로 Moore Tree 알고리즘 입니다.

알고리즘 내용 파악 및 분석, 예제 풀이와 C 프로그램 구현 까지 되어 있습니다.

목차

Ⅰ 서론
1. 개요
2. Tree & Vine building Algorithm
Ⅱ 본론
1. Moore Tree Algorithm
2. Moore Tree algorithm
3. 예제 풀이
4. Programming
Ⅲ 결론

본문내용

2. Moore Tree algorithm

1) 기본개념
․Tree는 순환(loop)없이 node가 연결되어 있는 network이다.
․Moore 알고리즘에서는 현재의 도착 node가 다음 단계에서의 출발 node(NEXT)가 되 며 계속적으로 새로운 ENTRY를 사용한다.
․이 과정에서 만일 출발 node에서 특정 node까지가 최단이 아니면 보다 짧은 경로로 대치시키는 과정을 반복해 최단 경로를 결정하게 된다.
․모든 node를 연결해 가며 최소의 통행비용으로 갱신하며 이전 node를 기록해나가면 출발 node에서 모든 node를 연결하는 최단경로를 도출할 수 있게 된다.

2) 용어설명
․tree : 한 기점에 대해 어떤 알고리즘을 통해 각 종점까지 연결되는 단 하나의 경로만 존재할 경우, 이를 최소비용수형망(minimal cost tree) 또는 간간히 수형망(tree)이라 하 고 이런 종류의 알고리즘을 tree building algorithm이라 한다.
최단경로 탐색시 전노드만을 고려하는 것으로 이는 링크비용만이 고려된다
․h (home) : 기점이 되는 시점 node (origin node)
․Next : 판단단계에서의 분석의 중심 대상이 될 node
․Working table L : tree building 과정에 따라 해당하는 node를 진입시키는데 사용하는 table을 말하며 loose-ends table이라고도 한다.
․Tree table R : network에 있는 모든 node에 대한 선행노드 번호, 시점부터 해당 node 까지의 비용 등에 대한 값을 담고 있는 table
․network table A : network를 구성하는 모든 link에 대한 기․종점 node 번호 및 비용 등에 대한 값을 담고 있는 table
․predecessor link (선행링크) : node , , 가 서로 연결되어 있을 때, link(,)를 link (,)의 predecessor link 라고 한다.
․predecessor node (선행노드) : link(,)에서 node 를 node 의 predecessor node라고 한다.
․ : 시점부터 node 까지의 최소비용
․ : 시점부터 node 까지의 잠정적인 최소비용, 최종적인 값은 와 같다.
․ : node 의 선행 node
․C next k : next 노드에서 노드까지의 링크 비용

참고 자료

yosef sheffi “urban transportation networks”
Roy Thomas “Traffic Assignment Techniques” (1991)
Dimitri P. Bertsekas “Linear Network Optimization : Algorithms and Codes“ (1991)
이재규, “c로배우는 알고리즘 2001 세화”
최재성,원재무 “(개정판)교통공학”