최단 경로 알고리즘 비교

1. 다익스트라 알고리즘 (Dijkstra's Algorithm):
   •    특징: 다익스트라 알고리즘은 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 음의 가중치가 없는 그래프에서 사용됩니다.
   •    알고리즘 사용하는 상황: 음의 가중치가 없는 그래프에서 사용되며, 최단 경로를 찾아야 하는 경우에 활용됩니다.
   • 알고리즘 동작 과정:
     1. 출발 정점을 기준으로 초기화합니다.
     2. 출발 정점에서부터 각 정점까지의 최단 경로를 갱신합니다.
     3. 방문하지 않은 정점 중에서 최단 거리가 가장 짧은 정점을 선택하여 방문합니다.
     4. 해당 정점을 경유로하여 인접한 정점까지의 거리를 갱신합니다.
     5. 위 과정을 모든 정점을 방문할 때까지 반복합니다.
2. 벨만-포드 알고리즘 (Bellman-Ford Algorithm):
   •    특징: 벨만-포드 알고리즘은 음의 가중치를 포함한 그래프에서도 사용 가능한 단일 출발점 최단 경로 알고리즘입니다. 하지만 음수 사이클이 존재하는 경우 이를 탐지할 수 있습니다.
   •    알고리즘 사용하는 상황: 음의 가중치가 포함되어 있거나 음수 사이클을 감지해야 하는 경우에 사용됩니다.
   • 알고리즘 동작 과정:
     1. 출발 정점을 기준으로 초기화합니다.
     2. 모든 간선에 대해 반복하여 각 정점까지의 최단 거리를 갱신합니다.
     3. 모든 간선에 대해 한 번 더 반복하면서 음수 사이클이 존재하는지 확인합니다.
3. 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm):
   •    특징: 플로이드-워셜 알고리즘은 그래프의 모든 정점 사이의 최단 경로를 찾는 알고리즘입니다. 음의 가중치를 포함한 그래프에서도 사용 가능합니다.
   •    알고리즘 사용하는 상황: 모든 정점 사이의 최단 경로를 찾아야 하는 경우에 사용됩니다.
   • 알고리즘 동작 과정:
     1. 초기 그래프를 인접 행렬로 표현합니다.
     2. 모든 정점을 중간 정점으로 가정하여 최단 경로를 계산합니다.
     3. 인접 행렬을 갱신하여 더 짧은 경로를 찾습니다.
     4. 위 과정을 모든 정점에 대해 반복하여 최종적인 최단 경로를 찾습니다.