데이크스트라 알고리즘: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 →알고리즘: 책<<알고리즘 문제해결전략>>에 나오는 용어로 수정 |
→설명: 그림 추가 |
||
41번째 줄:
== 설명 ==
[[파일:다익스트라 갱신.png|섬네일|아래쪽 교차로가 현재 위치일 때 갱신되는 상황을 나타낸 그림이다. 각 교차로에는 현재까지의 최단 거리가 적혀있다. 현재 위치에서 이웃 교차로까지 5의 거리로 갈 수 있다고 할 때, 이웃교차로에는 15의 거리로 도착할 수 있다. 왼쪽 교차로는 이미 다른 경로를 통해 13의 거리로 도착할 수 있으므로 갱신하지 않고, 오른쪽 교차로는 더 짧은 거리로 도착할 수 있으므로 갱신한다. 가운데 교차로는 방문하지 않은 교차로이므로 갱신한다. 이 과정은 현재 거리와 도로 길이를 더한 값과 교차로에 쓰여진 값을 비교해서 구할 수 있다.]]
:'''''참고:''' 이 문단에서는 이해를 돕기 위해서 '''교차로''', '''도로''' 그리고 '''지도'''라는 용어를 사용했지만, 공식적인 용어는 각각 '''꼭짓점''', '''변''' 그리고 '''그래프'''이다.''
| |||