Shortest Path Problem #

Find similar titles

총 3회 업데이트 됨.

Edit

최초 작성자
Duskan 2016-11-24 07:25:12
최근 업데이트
KyujinLee 2016-11-29 11:11:57

Structured data

Category: Computer science; Algorithm

Shortest Path Probelm(최단거리 문제) #

최단거리 문제(Shortest Path Algorithm)는 Computer Algorithm의 대표적인 문제중 하나로 Graph 에서 A Node에서 B Node로 가는 가장 빠른 길(비용이 가장 적게 소모되는 길)을 찾는 문제이다. 최단거리 문제는 그래프의 특성이 Undirect, Direct, Mixed에 따라 또 Edge의 Weight가 있는지, Weight에 음수값이 들어가는지에 따라 필요한 알고리즘이 조금씩 다르며 뒤쪽으로 갈 수록 구현이 복잡해진다.

다익스트라 알고리즘(Dijkstra Algorithm) #

다익스트라 알고리즘은 Edge가 Undirect, Direct 상관없이 적용가능하며 다만 Edge의 Weight가 음수일 경우 이 알고리즘은 적용이 불가능하다는 단점이 있다.

다익스트라 알고리즘의 기본 방법은 다음과 같다.

시작 노드로부터 전체 노드에 대해 각 노드의 거리를 임의의 큰 값을 부여한다. 임의의 값은 예상되는 도달 값보다 충분히 큰 값을 두어야 하며, 주로 무한대 값을 많이 부여한다.
시작위치를 현재 위치로 설정한다. 그리고 현재 자신이 있는 위치를 제외한 모든 노드를 방문하지 않은 노드라고 설정한다.
시작위치로부터 현재 위치로 갈수 있는 모든 가능성을 고려하여 시작위치로부터의 거리를 계산한다. 이때 계산한 결과가 기존의 결과보다 더 작은경우 현재 위치의 거리를 갱신한다. 이를 응용하여 휴리스틱 알고리즘(Heuristic Algorithm)도 적용 할 수 있다. 만약 이미 방문한 노드가 있다면, 시작점부터 방문한 노드까지의 거리는 이미 계산 후 저장되어 있기 때문에 이를 이용하면 경우의 수를 줄일 수 있다.
3번 과정의 결과로 시작위치로부터 현재위치까지 가장 짧은 거리를 저장했다면, 현재 위치를 방문한 노드로 표시하고, 이웃 노드로 이동한다. 이제 시작위치로부터 방문한 노드까지의 거리는 이미 계산되었으므로 다시 계산하지 않는다. 다시 현재위치에 대해 3번 작업을 수행한다.
자신이 찾고자하던 노드가 방문노드로 바뀌었거나, 더이상 방문할 수 있는 노드가 없는경우 알고리즘을 종료한다. 자신이 찾고자하던 노드가 방문노드로 바뀌었다면, 시작위치부터 찾고자 한 노드까지의 거리를 구할 수 있다.

Structured data

Shortest Path Probelm(최단거리 문제) #

다익스트라 알고리즘(Dijkstra Algorithm) #

Suggested Pages #