[자료구조] 다익스트라의 최단 경로

• 각 간선에 대한 정보를 우선순위 큐에 담아 처리하는 방식(프림 알고리즘과 흡사)
• 음의 간선이 없을 때 정상적으로 동작하는데 현실에서는 음의 간선이 존재하지 않으니 현실세계에 적합 동작 방식
• 다익스트라의 원래 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘
• 더 일반적인 변형은 한 꼭짓점을 소스 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것

 

다익스트라의 최단 경로 작동 순서

1. 그래프의 시작점을 선택하여 트리 T에 포함시킴
2. T에 포함된 노드와 그렇지 않은 노드 사이의 간선 중에서 '이동거리'가 가장 작은 간선을 찾음
3. 해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함시킴
4. 모든 노드가 포함될때까지 반복

이미지 출처 : Wikipedia

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수