회원가입

[그래프] 24. 최단 경로 알고리즘이란?

NULL 2021-09-27

최단 경로란?

그래프에서 경로라는 것은 두 Node 사이를 이어주는 길이다.

 

아래와 같은 그래프가 있다고 가정하자

 

'지웅'에서 '규리' Node까지 가는 이 길을 보자.

바로 이 길이 지웅 - 소원 - 규리 경로 이다.

'지웅'에서 '규리'까지 가는 경로가 하나만 있는 것이 아니다.

 

지웅 - 현승 - 소원 - 규리경로도 '지웅'과 '규리'를 이어준다.

 

모든 경로에는 거리라는 것이 있다.

지금은 비가중치 그래프를 보고 있으니까, 거리는 경로 안에 있는 엣지의 수이다.

지웅 - 소원 - 규리 경로는 엣지가 2개 있으니까 거리가 2이다.

지웅 - 현승 -소원 -규리 경로는 엣지가 3개 있으니까 거리는 3이다.

 

최단 경로는 두 Node 사이에 존재할 수 있는 모든 경로 중, 거리가 가장 짧은 경로이다.

영어로 경로path라서 최단 경로shortest path 라고 한다.

 

지하철을 탈 때 가장 빠르게 원하는 역까지 가는 방법을 구하고 싶을 때, SNS에서 두 사람이 몇 다리를 건너서 아는 사이인지 측정하고 싶을 때, 이럴 때, 모두 최단 경로를 구해야 한다.

 

이 방법을 최단 경로 알고리즘 이라고 부른다.

그래프 안에서 최단 경로를 구하는 알고리즘은 무수히 많다.

 

같은 그래프여도 엄청 다양한 특징들이 있다.

방향 그래프, 무방향 그래프, 가중치 그래프, 비가중치 그래프, 엣지 중에 음수값을 갖는 엣지가 있는지, 싸이클이 있는지 없는지 등

이런 다양한 특징들이 있다.

 

이렇게 그래프의 특성에 때라 사용되는 최단 거리 알고리즘이 다르다.

 

이번 챕터에서는 두 개의 대표적인 최단 경로 알고리즘을 알아볼 것이다.

  • BFS → 살짝만 변경하면 최단 경로를 알아내는 알고리즘으로 쓸 수 있다.

    (단, 비가중치 그래프에서만 최단 경로를 구할 수 있다.)

  • **Dijkstra(**다익스트라)

    (가중치 그래프 이용)

0 0