반응형 프로그래머의 길/알고리즘22 Dijkstra Algorithm Shortest Path - Dijkstra Algorithm 방향그래프(Directed Graph)의 간선이 양수의 Weight를 가질 때 임의의 출발 정점에서 도착 정점까지의 경로 중 경로의 길이가 최소인 경로를 최단경로라고 정의한다. 이러한 최단경로는 도로망, 항공로 지도, 작업공정계산 등에 널리 응용된다. 최단경로는 다익스트라의 알고리즘으로 구할 수 있다. 다익스트라의 알고리즘 인접행렬 상태로 각 간선의 가중치(Weight)가 존재하도록 한다. 정점 i에서 i까지의 가중치는 0이고 정점 i에서 j까지의 간선 E(i, j)가 존재치 않으면 가중치는 무한대(∞)가 된다. 집합 S와 T를 정하는데 S는 출발 정점을 초기값으로 하고 집합 T는 출발 정점을 제외한 모든 정점을 포함하도록 초기화한다. 출발 .. 2009. 2. 2. Dijkstra Algorithm Dijkstra Algorithm 동적 혹은, Adaptive즉, 적응적 Routing기법 알고리즘등으로 불리는 유명한 알고리즘에 대해 공부했던 내용을 Review한다.또한 Dijkstra’s Algorithm에 대해서도 언급하고 있다. Picture 1. example of Dijkstra’s Algorithm Source node를 1이라고 하고, Destination Node를 8이라고 할 때, 인접배열을 위한 table이 위처럼 작성될 수가 있다. 처음 1의 입장에서 2와 6은 인접해 있기에 그 거리를 기록할 수가 있다. 즉 알수 있다고 보는 것이다. 이에 반해서, 나머지 node는 보이지 않는다. 아득한 거리로 보자는 것이다. 역시 만약 2번 path를 타기로 결정했다면, 2에서 볼 때, 1,3.. 2009. 2. 2. qsort 함수에 대하여.. 2007. 4. 3. 이진탐색 (Binary Search) 알고리즘 이진탐색 (Binary Search) 알고리즘. N개의 데이터를 가진 배열 list[]가 있고, 우리가 찾고자 하는 값이 key라고 하자( list[0], list[1], ..., list[N-1] ). 이진 탐색은 배열의 중간요소(list[N/2])와 찾고자하는 값(key)을 비교한다. 찾고자하는 값이 중간요소 보다 작다면 배열의 중간요소 보다 큰 요소들(list[N/2] ... list[N-1])에는 찾고자 하는 데이터가 없는 것이다. 즉, 데이터의 절반은 검사 할 필요가 없어진다. 나머지 요소들에 대해 똑같이 반복한다. (Recusive) 탐색방법 입력 : 리스트,시작인덱스,마지막인덱스,검색값 출력 : 해당 키의 인덱스 ( 찾는 값이 있으면 ) 또는 아니오 ( 찾는 것이 없으면) 1. 각 값의 의미.. 2007. 4. 3. 이전 1 2 3 4 ··· 6 다음 반응형
