목록최단 경로 (1)

codinging

[알고리즘] 최단 경로 알고리즘 다익스트라(Dijkstra) 알아보기

최단 경로 알고리즘 최단 경로 알고리즘이란 가중치가 주어진 그래프에서 두 노드의 경로중 간선의 가중치의 합이 최소가 되는 경로를 찾는 알고리즘이다. 다익스트라 : 특정 한 노드에서 모든 노드 까지의 최단거리(음수 x)벨만-포드 : 다익스트라의 음의 가중치가 사이클을 형성해 무한히 작아지는걸 보안하기 위해 나옴플로이드-위셜 : 모든 노드간 최단거리 🦝 다익스트라 특정 한 노드에서 모든 노드 까지의 최단 거리를 구하는 알고리즘이다. (간선의 가중치가 음수이면 안된다는 조건이 있다.) 방문 하지 않은 경로중 가중치가 최소인 노드를 선택해 거리를 확정 해 나가는 형식이다. 0. Dist 의 값을 INF로 초기화 시켜준다. 1. 방문한 노드와 연결 된 노드의 Dist를 비교해 업데이트를 시켜주고, 현재 방문 노드..
Algorithm 2023. 7. 10. 10:45
이전 Prev 1 Next 다음