최단거리&다익스트라 알고리즘 개념

최단거리 알고리즘

최단거리 알고리즘은 지하철 노선도, 네비게이션 등 다방면에 사용되는 알고리즘

• 다익스트라 최단 경로 알고리즘
• 플로이드 워셜 알고리즘
• 벨만 포드 알고리즘

다익스트라 알고리즘

• 그래프에서 여러 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 음의 간선이 없을 때 정상적 작동
• GPS 소프트웨어의 기본 알고리즘
• 기본적으로 그리디 알고리즘으로 분류

1. 출발 노드와, 도착 노드를 설정
2. 알고 있는 모든 거리 값을 부여
3. 출발 노드부터 시작하여, 방문하지 않은 인접 노드를 방문, 거리를 계산한 다음, 현재 알고있는 거리보다 짧으면 해당 값으로 갱신한다.
4. 현재 노드에 인접한 모든 미방문 노드까지의 거리를 계산했다면, 현재 노드는 방문한 것이므로, 미방문 집합에서 제거한다.
5. 도착 노드가 미방문 노드 집합에서 벗어나면, 알고리즘을 종료한다.