Hani_Levenshtein

다익스트라와 벨만-포드 알고리즘은 시작점이 정해져 있어서 모든 쌍에 대한 최단 경로를 알아낼 수 없었습니다. 물론, 단일 시작점 알고리즘을 여러 번 돌린다면 모든 쌍에 대한 최단 경로를 찾아낼 수 있지만, 시간 복잡도와 알고리즘 구현 측면에서 한번만 실행해도 되는 플로이드-와샬 알고리즘이 더 적합한 선택일 것입니다. 2020/08/31 - [알고리즘] - 다익스트라 알고리즘 2020/09/07 - [알고리즘] - 벨만포드 알고리즘 2020/09/07 - [알고리즘] - SPFA (Shortest Path Faster Algorithm) 플로이드-와샬 알고리즘은 벨만-포드 알고리즘과 동일하게 음수 가중치가 있어도 사용 가능합니다. 플로이드-와샬 알고리즘의 동작 과정을 알아봅시다. 먼저, 모든 쌍의 최단 경..

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