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

둘러보기로 가기 검색하러 가기
(→‎정확성의 증명: 문맥 수정)
 
== 정확성의 증명 ==
''데이크스트라 알고리즘의 증명은알고리즘은 방문한 꼭짓점의노드 위의 숫자를 이용하여 귀납적으로 숫자의증명할 추론으로 이루어진다있다.''
 
''불변의 가설'': 방문한 꼭짓점 {{모노|v}}에 대해서, {{모노|dist[v]}}는 {{모노|source}}에서 {{모노|v}} 까지의 최단 거리로 간주하며, 미방문 꼭짓점 {{모노|u}}에 대해서는 {{모노|dist[u]}}를 방문한 꼭짓점 만을 통하는 {{모노|source}}에서 {{모노|u}}까지의 최단 거리로 간주한다. 이 가정은 경로가 존재할 때만 고려하지만, 존재하지 않으면 거리는 무한대로 설정된다. (참고 : 미방문 꼭짓점에 대해서는 {{모노|dist[u]}}를 실제 최단 길이로 간주하지 않는다)

편집

305

둘러보기 메뉴