728x90
Dijkstra
-
다익스트라 알고리즘(Dijkstra Algorithm)Computer Science/Algorithm 2021. 9. 25. 18:38
다익스트라 알고리즘이란? - 그래프 상의 한 노드에서 다른 모든 노드까지의 최단 거리를 구할 때 유용하게 사용되는 알고리즘이다. - 노드와 노드 사이의 간선의 가중치가 0 이상의 정수일 때만 사용이 가능하다. 다익스트라 알고리즘의 동작 과정 1단계 노드 1 2 3 4 5 6 거리 0 2 5 1 INF INF - 출발 노드인 1을 기준으로 인접한 노드인 2, 3, 4 노드에 대한 최단 거리 테이블을 만들어 준다. - 인접하지 않은 노드인 경우 무한으로 표시한다. 2단계 노드 1 2 3 4 5 6 거리 0 2 1+3=4 1 1+1=2 INF - 노드 1과 인접한 노드들 중 최단 거리가 가장 짧은 노드인 4번으로 진행한다. - 노드 4와 인접한 노드는 3, 5 노드이고, 이 노드까지의 최단 거리와 기존의 최단..