Hani_Levenshtein

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