최단거리 확인하기

다음은 각 지점을 연결하는 도로 상황을 나타내는 그림이다. 각 도로는 화살표를 따라 일방통행만 가능하며 화살표 위에는 도로 이용 시 드는 비용이 쓰여 있다. A지점부터 K지점까지 가는데 드는 최소 비용은 얼마인가?

출처 : 정보올림피아드 2007년 초등부 13번

 

정답) 9

 

이렇게 찾아가는 알고리즘으로는 다익스트라 알고리즘이 있다.

A,B,C,D,E,F,G,H,I,J,K 

0,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF

먼저 위와 같이 A출발점만 0 을 설정하고 A에서 갈 수 있는 곳을 A까지 온 거리 누적해서 최단거리를 설정한다.

A,B,C,D,E,F,G,H,I,J,K

0,3,1,5,INF,INF,INF,INF,INF,INF,INF

여기서 그 다음 방문하지 않은 곳에서 가장 짧은 C를 선택해서 C까지 온 거리 누적해서 그 다음 갈 곳을 설정한다.

A,B,C,D,E,F,G,H,I,J,K

0,3,1,5,INF,4,INF,INF,INF,INF,INF

그 다음 방문하지 않은 곳 중에서 가장 작은 거리는 B이므로 B까지 온 거리 누적해서 B에서 갈 수 있는 곳을 설정한다.

A,B,C,D,E,F,G,H,I,J,K

0,3,1,5,5,4,INF,INF,INF,INF,INF

이러한 규칙으로 계속 진행하면 위의 그림과 같은 최단 거리를 구할 수 있다.

 

실제 문제 풀이에서는 이러한 알고리즘으로 찾기 보다는 직관적으로 짧은 거리를 찾아 가는 것이 유리하다.