"데이크스트라 알고리즘"의 두 판 사이의 차이

둘러보기로 가기 검색하러 가기
(222.118.64.55(토론)의 24101517판 편집을 되돌림)
태그: 편집 취소
# 모든 꼭짓점을 미방문 상태로 표시한다. ''미방문 집합''이라는 모든 미방문 꼭짓점의 집합을 만든다.
# 모든 꼭짓점에 시험적 거리 값을 부여한다: 초기점을 0으로, 다른 모든 꼭짓점을 무한대로 설정한다. 초기점을 현재 위치로 설정한다.
# 현재 꼭짓점에서 미방문 인접 꼭짓점을 찾아 그 ''시험적'' 거리를 현재 꼭짓점에서 계산한다. 새로 계산한 ''시험적'' 거리를 현재 부여된 값과 비교해서 더 작은 값을 넣는다. 예를 들어, 현재 꼭짓점 ''A''의 <!--시험적 ((이 거리는 '''시험적 거리가 아니기''' 때문에 주석 처리 했습니다.. 이 값은 인접 꼭짓점을 방문할 때 바뀔 수 없습니다.. 따라서 이것을 시험적이라고 부르는 것은 아직 바뀔 수 있다는 것을 의미하므로 혼동을 줄 수 있습니다))-->거리가 6이라고 표시되었고, 인접 꼭짓점 ''B''으로 연결되는 변의 길이가 2라고 한다면, ''A''를 통한 ''B''까지의 거리는 6 + 2 = 8이 될 것이다된다. B가이전의 이전에''B''까지의 거리가 8보다 크다고 표시되었었다면컸다면 8로 바꾸고, 그렇지 않다면 그대로 놔둔다.
# 만약 현재 노드에꼭짓점에 인접한 모든 미방문 꼭짓점을꼭짓점까지의 거리를 계산했다면, 현재 꼭짓점을 방문한 것으로 표시하고 ''미방문 집합''에서 제거한다. 방문한 꼭짓점은 이후에는 다시 검사하지방문하지 않는다.
<!-- 이 거리는 마지막이며 최솟값으로 기록된다. ((거리는 큐에서 꺼내어 다루고 있던 현재 위치에 대해서 마지막이기 때문에 주석 처리했습니다.. 이 거리는 인접 꼭짓점을 방문하는 동안 줄어들 수 없습니다.. 하지만 현재 꼭짓점은 이 단계 전까지는 미방문 상태입니다. 이 점은 일관적이지 않으며 혼란을 줍니다.)) -->
<!-- # 시험적 거리가 가장 작은 다음 미방문 꼭짓점으로 이동하고 위의 인접 꼭짓점을 계산하고 방문한 상태로 표시하는 단계를 반복한다. ((이 줄은 아래의 내용과 동일하며, 무한루프를 형성하고, 설명이 더 모호합니다)) -->
# 두 꼭짓점 사이의 경로를 찾는 경우: 도착점이 방문한 상태로 표시되면 멈추고 알고리듬을 종료한다.
# 도착점이 방문한 상태로 표시되거나 (특정 두 꼭짓점완전 사이의순회 경로를 계획하고찾는 있을 때)경우: ''미방문 집합''에 있는 꼭짓점들의 시험적 거리 중 최솟값이 무한대이면(완전 순회를이는 계획중일 때. 이 현상은 초기점과 나머지출발점과 미방문 집합 간에사이에 연결이 없을없는 경우이므로 일어난다), 멈춘다.멈추고 알고리즘을 종료한다.
# 아니면 시험적 거리가 가장 작은 다음 미방문 꼭짓점을 새로운 "현재 위치"로 선택하고 3단계로 되돌아간다.
 

둘러보기 메뉴