최단거리 찾기(Shortest Path) 하나의 노드쌍에서 최단 거리를 찾습니다. 길찾기 알고리즘은 19세기 부터 유래를 찾을 수 있고, 1956년 Edsger Dijkstra(다익스트라, 데이크스트라)가 가장 유명한 알고리즘을 만들었으며, 대체루트 찾기로 유명해졌습니다. 이 알고리즘을 이해해 보도록 하겠습니다. 위의 움짤을 하나씩 그려가면서 이해해보도록 하겠습니다. 그래프의 구성 그래프의 기본 구성은 다음과 같습니다. 6개의 노드와 8개의 엣지로 이루어져 있습니다. 실생활에 대응해서 생각해본다면 6개의 도시와 이 도시들을 잇는 8개의 도로망이라고 생각해도 됩니다. 그리고 8개의 엣지 위의 값은 거리라고 생각합시다. 최단거리 = 최소 걸리는 루트 라는 공식을 성립하게 하기 위해, 도로체증, 신호 등등의 ..
