다익스트라 알고리즘(Dijkstra)

다익스트라 알고리즘(Dijkstra)

정의

• 최단 경로 알고리즘
• 가중치는 양수만 가능
  • 가중치가 음수인 경우에는 벨만-포드 혹은 플로이드-워셜 알고리즘 사용
  • 대부분의 일상생활에서는 양수의 가중치만 있기 때문에 다익스트라를 사용함

배열로 표현

1. 노드의 번호와 배열의 인덱스를 일치시킨다.
2. 시작지점부터 시작해서 하나씩 이동할 수 있는 노드의 인덱스 위치에다가 최소값을 업데이트 한다.
3. 각 노드별로 계속 반복하면서 나올 수 있는 최소값이 나오면 그때마다 업데이트시킨다.
4. 최종 목적지 노드까지 계속 반복한다.