[Algorithm] Shortest Path - 최단경로 알고리즘

최단 경로 알고리즘이란,
최단 경로 알고리즘으로 주어진 노드와 간선들 중 가장 짧은 경로를 찾는 알고리즘

최단 경로 문제의 종류

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

최단 경로 알고리즘의 종류

• 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제
  • 간선의 가중치가 모두 같은 그래프일 경우 : BFS 이용
  • 간선의 가중치가 각각 다른 그래프일 경우 : Dijkstra, Bellman-Ford(음수의 가중치 간선 존재하는 경우) 이용
• 각 모든 정점에서 다른 모든 정점까지 최단 경로를 구하는 문제 : Floyd-Warshall 이용

Dijkstra Algorithm

• A→C로 갈 때 A→B→C로 가는 경로의 가중치 합이 A→C의 가중치 합보다 작다면 B를 거쳐가는 경로를 선택하는 알고리즘

Bellman-Ford Algorithm

• 음의 가중치가 있을 때에 사용할 수 있는 알고리즘

Floyd-Warshall Algorithm

• A, B, C의 정점이 있다면 A와 B, C 정점 간의 최단경로, 또 B와 A, C 정점 간의 최단경로 C와 A, B 간의 최단 경로를 구함
• 즉, 모든 정점에서 다른 모든 정점 간의 최단 경로를 구하는 알고리즘