다익스트라(dijkstra)

최단 경로 알고리즘

1. 그래프에서 특정 정점에서 목적지까지 최단 경로를 구하는 알고리즘이다.
2. 이전에 배운 bfs, dfs도 최단경로 알고리즘으로 사용가능하다.
3. bfs, 다익스트라, 벨만-포드, 프로이드 와샬 알고리즘 등이 존재한다.

그래프의 간선에 가중치 값이 존재하지 않은 경우에는 BFS, DFS를 이용하여 최단경로를 찾는 경우가 많으며, 간선마다 가중치 값이 존재하는 경우에는 다익스트라 알고리즘을 사용하는 것이 유리하다.

다익스트라 알고리즘이란?

1. 우선순위 큐를 이용하여 만들 수 있다.(Heap)
2. 시간복잡도는 V가 정점의 수, E가 간선의 수 일 때 O(E logV)이다.

flow

1. 시작점을 제외한 모든 정점의 거리를 무한으로 설정하고, 시작점은 0으로 설정한다.
2. 시작점을 선택한다.
3. 선택한 정점에서 갈 수 있는 정점의 거리를 정점값 + 간선값으로 갱신한다.
4. 선택한 정점을 방문처리한다.
5. 이미 방문한 정점과 무한인 정점(연결되어 있지 않은 정점)을 제외하고 가장 최단거리인 정점을 선택한다.
6. 더 이상 방문할 수 있는 정점이 없을 때 까지 3~5를 반복한다.
7. 도착지점의 값을 확인한다.