[알고리즘] 최단경로 알고리즘 종류 (BFS,다익스트라,플로이드와샬,벨만-포드)

(정점=노드 같은 뜻! 혼용해서 사용할 시 혼동 방지!)

 

그래프에서 각 정점끼리 사이의 최단 거리를 구하는 알고리즘 방법은 여러 가지가 있다. 문제에 따라 효율적인 방법이 다르므로 잘 선택해서 사용해야 한다.

 

문제의 종류

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

응용으로 한 중간 정점을 거쳐서 가는 최단경로 등 다양한 문제의 종류에 적용하여 사용할 수 있다.

 

 

 

 

알고리즘 종류

 

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

-간선의 가중치가 모두 같은 그래프일 경우

 

• BFS

 

-간선의 가중치가 각각 다른 그래프일 경우

 

• 다익스트라
• 벨만-포드 → 음수 가중치의 간선이 존재할 때

 

 

 

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

• 플로이드 와샬

 

 

 

 

1. 다익스트라(Dijkstra) 알고리즘

간단히 예를 들어보면 A->C로 갈 때 A->B->C 가는 경로의 가중치 합이 A->C의 가중치 합보다 작다면 B를 거쳐가는 경로를 선택하는 알고리즘이다.

 

문제풀이를 통한 코드, 알고리즘 방법 정리

 

2. 벨만-포드(Bellman-Ford) 알고리즘

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

 

 

3. 플로이드-와샬(Floyd-Warshall) 알고리즘

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

 

문제풀이를 통한 코드, 알고리즘 방법 정리

 

 

 

 

 

공부하다가 추가할 내용이나 문제가 있으면 추가&수정할 예정!