개요

• 최단 경로는 가중치 그래프에서 두 정점을 연결하는 경로 중 가중치의 합이 최소인 경로를 말한다.
• 최단 경로를 구하기 위해서는 그래프에 음수인 가중치가 있어서는 안되고, 간선이 없을 경우 무한대 값으로 저장한다.
• 최단 경로를 구하는 알고리즘에는 다익스트라 알고리즘과 이를 변형 시킨 에이스타 알고리즘이 있다.

다익스트라 알고리즘

• 다익스트라 알고리즘은 무방향 그래프, 방향 그래프 모두에 적용 가능한 알고리즘이다.
• 기본 원리는 시작 정점에서 가장 가까운 정점을 선택하여 추가하면서 추가된 모든 정점에 대한 최단 경로를 구해가는 과정이다.
  

구현

• C#으로 구현하면 아래와 같다.