최단 경로 탐색

최단 경로 탐색

그래프 상에서 정점 간의 탐색 비용을 최소화하는 알고리즘

탐색 원리

그래프의 간선 가중치에 따라 경로를 선택하여 최소한의 비용(거리, 시간)을 찾는다.

해당 경로를 선택하는 방식에 따라 아래와 같이 다양한 종류의 알고리즘으로 나뉜다.

알고리즘의 종류

• Dijkstra

  한 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘

• Bellman-Ford

  한 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘

• Floyd-Warshall

  모든 정점에서 정점간 최단경로를 구하는 알고리즘