Hani_Levenshtein

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

최단 경로 문제는 그래프에서 두 정점 사이의 가중치 합이 최소가 되는 경로의 길이를 찾는 문제입니다. 문제를 풀기 전에 아래의 상황을 고려해야 합니다. 1. 음수 가중치가 있는가 2. 시작점이 주어지는가 최단 경로 알고리즘에는 크게 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘이 있습니다. 위에서 언급한 조건을 생각하여 어떤 알고리즘을 사용할지 선택해야하는데, 동일한 알고리즘이라도 구현 방식에 따라 알고리즘 성능이 좌우됩니다. 먼저, 1번을 고려해봅니다. 음수 가중치를 거쳐간다면 경로의 길이가 짧아지기 때문에 최단 경로를 결정할 때, 매력적인 선택지입니다. 그러나, 음수 가중치를 가진 경로가 사이클을 이루는 경우(한바퀴 돌았을 때의 합이 음수)가 있다면, -INF로 경로의 길이가 발산..