최단경로 적용 사례

소개글

경영과학이나 컴퓨터공학의 자료구조 알고리즘에서 쓰이는

최단경로 이론이 실제 어떠한 방법으로 적용되는지에 대한 보고서

경영학 전공중 OR분야, 컴퓨터공학 또는 경영정보학의 자료구조, 알고리즘분야의 자료

목차

없음

본문내용

네트워크모형에 최단경로기법을 소개하고 있다. 하지만 이것을 상세히 분류하자면, 최단경로기법을 2가지로 구분할 수 있는데, 첫 번째는 그리디 기법(Greedy method)인 다익스트라 기법(Dijkstra method)과, 동적계획법(Dynamic Programming)인 플로이드 알고리즘(Floyd Algorithms)으로 나눌 수 있다. 이번 보고서에서는 이 2가지 방법이 어떠한 원리로 최단경로를 찾아내는 지에 대해서 소개하겠다.
첫 번째로 그리디 기법(Greedy method)에 대해서 알아보도록 하겠다. 그리디 기법(Greedy method)의 원어를 우리말로 풀어보면 욕심쟁이 방법이라고 말 할 수 있다. 즉 전후 상황을 파악하지 않고, 현재 시점에서 가장 최적의 상황을 찾아서 경로를 파악해 나가는 것이다. 이러한 기본적 원리로 최단경로를 구해낸 방법이 다익스트라 방법(Dijkstra method)인데, 다익스트라(Dijkstra)라는 사람이 만들었다고 해서 그의 이름을 붙여서 다익스트라 방법(Dijkstra method)라고 한다. 그럼 이 다익스트라 방법이 구체적으로 어떠한 원리로 최단경로를 찾아내는가에 대해서 알아보겠다. 다익스트라 방법은 한 시작점을 잡고서 그 시작점과 연결된 가장 짧은 거리의 정점을 찾아내가는 방식으로 최종 목적지까지 가장 짧은 거리를 찾아내 가는 방식이다. 다음 그림을 예로 구체적으로 설명해 보겠다.

참고 자료

없음