최단 경로 [ 수정 내역 ] [ 수정 ]

최근 수정: 6년 전

1. 개요

Shortest Path.

그래프에서 한 정점에서 다른 정점으로 갈 수 있는 경로 중에서 가중치 합이 가장 작은 경로.

상당히 많은 알고리즘들이 있으며, 학교에서는 자세히 배우지 않는다. [1]

2. 상세

가중치의 음수 여부, 구하고자 하는 정점의 개수 등에 따라 사용 가능한 알고리즘이 다르다.[2] 하지만 주로 많이 사용하는 것은 다익스트라 알고리즘.

가장 간단한 방법으로는 BFS로도 구할 수 있는데, 가중치가 1일 때만 사용한다. 자세한 건 아래 문서 참고.

2.1. BFS

간선의 가중치가 1일 때.

2.2. 다익스트라 알고리즘

간선의 가중치가 모두 양수일 때. 일반적으로는 이 알고리즘을 사용하면 된다.

2.3. 벨만-포드 알고리즘

간선의 가중치가 음수일 때도 사용 가능.

2.4. 플로이드-워셜 알고리즘

구하고자 하는 최단 경로의 정점이 여러개일 때. 여기서 정점은 경로의 시작 정점이다.

2.5. A* 알고리즘

휴리스틱 사용.

[1] 필자의 기억으로는 자료구조와실습 강의에서 다익스트라 정도만 했던 듯.

[2] 구하고자 하는 문제에 따라 적절히 선택 필요