벨만 포드 알고리즘 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점을 기준으로 다른 모든 정점까지의 최단경로를 구하여 결과적으로 원하는 도착지까지의 최단경로를 도출해 내는 알고리즘이다. 하지만 다익스트라 알고리즘과 다르게 그래프에 음의 가중치가 있어도 최단 경로를 구할 수 있다. [알고리즘] 다익스트라(Dijkstra) 다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍(DP)과 그리디 알고리즘을 활용한 최단경로 탐색 알고리즘이다. 다익스트라 알고리즘은 하나의 특정 정점에서 다른 모든 정점 dana-study-log.tistory.com 다익스트라와 음의 가중치 다익스트라 알고리즘 과정 1. 시작정점 선택 2. 거리 배열 초기화 (시작정점은 0으로 다른 노드는 무한대로) 3. 지금..
다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍(DP)과 그리디 알고리즘을 활용한 최단경로 탐색 알고리즘이다. 다익스트라 알고리즘은 하나의 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 알 수 있으며, 간선의 가중치가 양수일 때 사용가능하다. 다익스트라 알고리즘이 DP라고 할 수 있는 이유는 특정 최단 거리는 여러 개의 최단거리로 이루어져 있기 때문이며, 하나의 최단 거리를 구할 때 특정 정점까지의 최단거리 정보를 그대로 가져와 사용하기 때문이다. 또한 그리디 알고리즘이라고 말할 수 있는 이유는 특정 최단 거리에 최단 거리를 더해가며 최종적인 최단거리를 계산하는 방식이기 때문이다. (다익스트라 알고리즘을 공부한 뒤 다시 읽으면 쉽게 이해가능) 한 정점에서 다른 모든 정점까지의 최단거리를..
