[Algorithm] 최단 거리 알고리즘 총 정리

최단 경로 알고리즘을 만날 때 마다 어떤 알고리즘을 사용할지, 어떻게 사용하는지 헷갈려서 한번에 총 정리 해보았다.
참고 포스팅

최단 경로 알고리즘 종류

1. 가중치가 없거나 동일한 그래프
   • BFS (완전탐색 알고리즘)
     • 가중치가 없거나 동일한 그래프에서 BFS로 완전탐색하는 것이 최단경로 구하기에 가장 빠르다.
2. 가중치가 각각 다른 그래프
   1. 음수가 아닌 가중 그래프
      • 다익스트라(Dijkstra)
        • 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제
   2. 음수가 존재하는 가중 그래프
      • 벨만-포드 알고리즘(Bellman-Ford Algorithm)
        • 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제
      • 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)
        • 전체 쌍, 다수 출발, 단일 도착 최단 경로 문제
      • A* 알고리즘(A-star Algorithm)
        • 시작 노드에서 목표 노드까지의 최단 경로만

최단 경로 문제 유형

1. 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제
2. 각 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제
3. 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제

최단 경로 알고리즘 소개

1. 다익스트라(Dijkstra)
2. 벨만-포드 알고리즘(Bellman-Ford Algorithm)
3. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)
4. A* 알고리즘(A-star Algorithm)