벨만 포드 알고리즘

다익스트라 알고리즘은 하나의 시작점에서 주어진 모든 정점까지의 최단 경로의 길이를 알려주는 알고리즘으로, 간선의 가중치가 전부 양수인 경우에 한하여 적용할 수 있었습니다. 2020/08/31 - [알고리즘] - 최단 경로 알고리즘 - [1] 다익스트라 알고리즘 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 시작점이 정해져 있는 단일 시작점 알고리즘이지만, 음수 가중치에 있을 때에도 그래프 상의 모든 정점에 대한 최단 경로를 알아낼 수 있습니다. 이제 벨만-포드 알고리즘의 동작 과정을 예시로 알아보겠습니다 먼저, 시작점 1을 제외한 모든 정점의 최단 경로 길이를 Max 값으로 초기화 시켜줍니다. 시작점의 경로 길이는 0입니다. 정점 1에 붙어있는 모든 간선을 체크합니다. 1번 노드까지의 비용 + 1..
알고리즘 2020. 9. 7. 19:23
1