Dijkstra Algorithm

최단 경로 알고리즘 (Shortest Path)

그래프에는 어떤 정점에서 다른 정점으로의 사이를 잇는 최단 경로를 구하는 알고리즘이 존재한다.

 ( != MST )  MST : N-1개의 간선으로 최소 가중치 트리 만듦

 

그래프 내의 모든 간선의 가중치가 0 이상인 경우

=> Dijkstra 알고리즘을 이용한다.

 

그래프가 음수 가중치 간선을 포함하는 경우

=> Bellman-Ford 알고리즘을 이용한다.

 

 

 

 

Dijkstra 알고리즘

출발 정점으로부터 가장 가까운 아직 방문하지 않은 정점을 찾고,

다른 모든 정점까지의 거리에 대해서 선택된 정점을 지나서 가는 경우와, 직접 가는 경우 중 최솟값으로 최단 거리를 갱신해가면서

가장 가까운 정점을 하나씩 방문한 정점 집합에 추가하는 방식으로 최단 경로를 갱신.

(음의 간선이 있는 경우 사용 불가)

 

Bellman-Ford, Floyd Warshall 간략한 설명

Bellman-Ford는 음의 가중치를 가지는 간선이 있는 경우의 최단 경로 알고리즘

 

Dijkstra, Bellman-Ford 알고리즘 : 그래프의 한 정점에서 다른 정점으로 가는 최단 거리를 구하는 알고리즘

Floyd Warshall : 그래프의 모든 정점에서 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다. => O(n3)

 

 

 

• Dijkstra 수행 과정

출처 : https://travelbeeee.tistory.com/424

 

 

 

 

참고 : https://travelbeeee.tistory.com/424