최단 경로 알고리즘(다익스트라, 벨만-포드, 플로이드-와셜) 08 May 2021 in Dev on Algorithm 대표적인 그래프 내 특정 정점에서 갈 수 있는 모든 정점들까지의 최단 경로를 구하는 알고리즘들로는 다익스트라, 벨만-포드, 플로이드-와셜 알고리즘이 있다. 다익스트라 알고리즘다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 경로 를 구하는 알고리즘으로 큰 특징 중 하나는 간선의 가중치가 음수인 것이 하나라도 있다면 사용할 수 가 없다는 점 이다. 최단 거리는 여러개의 최단 거리로 이뤄져있기에 다익스트라 알고리즘은 동적 프로그래밍에 포함이 된다. 알고리즘 순서는 다음과 같다.
프로그래밍시 우선순위 큐를 이용하여 문제를 해결한다.
벨만-포드 알고리즘벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 하나의 정점에서 다른 모든 정점까지의 최단 경로 를 구하는 알고리즘이다. (RELAX 는 해당 정점에 대해서 더 낮은 가중치로 도달할 수 있는 경우, 그 값을 갱신해주는 것을 말한다) 플로이드-와셜 알고리즘플로이드-와셜 알고리즘은 모든 최단 경로를 다 구하는 알고리즘이다. 참고https://m.blog.naver.com/ndb796/221234424646 |