데이크스트라 알고리즘: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 →정확성의 증명: 문맥 수정 |
→정확성의 증명: 문맥 수정 - 일반인은 dist[]가 무엇을 의미하는지 모릅니다. |
||
138번째 줄:
데이크스트라 알고리즘은 방문한 노드에 쓰여진 숫자를 이용하여 귀납적으로 증명할 수 있다.
시작점에서 노드로 갈 수 있는 경로가 있는 경우, 방문한 노드 {{모노|v}}에 대해, {{모노|거리[v]}}는 시작점부터 {{모노|v}}까지 가장 짧은 거리이고, 방문하지 않은 노드 {{모노|u}}에 대해 {{모노|거리[u]}}는 시작점부터 {{모노|u}}까지 가장 짧을 것으로 추정되는 거리이다.
시작점에서 노드로 갈 수 없는 경우가 없다면 노드까지의 거리는 무한대로 둔다.
(참고 : 방문하지 않은 정점 {{모노|u}}에 대해 {{모노|거리[u]}}는 실제 최단거리가 아니다.)
기본적인 경우는 방문한 꼭짓점이 초기점인 {{모노|source}} 하나 밖에 없는 경우로, 이 가정은 [[자명성|자명하다]].
| |||