최단경로 알고리즘
최단경로 알고리즘는 그래프에서 간선의 가중치 합이 최소가 되는 경로를 찾는 행위이다. 최단경로 문제는 single-source 최단 경로, single-destination 최단경로, single-pair 최단 경로로 구분할 수 있다. single-source 최단경로는 임의의 하나의 정점에서 출발해 나머지 모든 정점까지의 최단 경로를 찾는 문제이다. 즉 출발은 한군데이고 끝나는 지점은 정해지지 않고 모든 정점에 대한 거리를 다 계산하면 된다. single-destination 최단경로는 모든 정점에서 출발해서 임의의 하나 정점까지의 최단 경로를 찾는 문제이다. 즉 도착지점만 정해져있어서 모든 출발 지점에 대한 최단경로를 구해야 한다. 이러한 문제는 완전 역으로 뒤집으면 single-source와 동일한 문제로 볼 수 있다. single-pair 최단경로는 모든 정점 쌍들 사이의 최단 경로를 찾는 문제이다.
BFS 알고리즘
BFS는 완전탐색 알고리즘 중 하나이며 가중치가 없거나 모든 가중치가 동일한 그래프에서 최단경로를 구하는 경우 가장 빠른 알고리즘으로 알려져 있다.
Dijkstra 알고리즘
음이 아닌 가중치 그래프에서 사용할 수 있는 알고리즘이고, 단일 쌍, 단일 출발, 단일 도착 최단 경로문제를 해결할때 사용된다. 일반적으로 현실세계에서는 간선이 음인 경우가 존재하지 않기 때문에 현실세계에서 많이 사용되는 알고리즘이다.
다익스트라 알고리즘은 V개의 정점과 음수가 아닌 N개의 간선을 가진 그래프 G에서 임의의 출발 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘이다.
Bellman-ford-moore 알고리즘
가중 그래프에서 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제를 해결할때 사용하는 알고리즘이다.
Reference
shortest path algorithm - Google 검색
Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.
www.google.com
'ALGORITHM > Algorithm 설명' 카테고리의 다른 글
| [알고리즘] 서로소 집합 - Disjoint Sets (0) | 2022.03.18 |
|---|---|
| [알고리즘] 그래프 이론 (0) | 2022.03.18 |
| [알고리즘] Binary Search (0) | 2022.02.28 |
| [알고리즘] Dynamic Programming (0) | 2022.02.15 |
| [알고리즘] BFS (Breadth First Search) (0) | 2022.02.04 |
