다익스트라 알고리즘

BFS를 이용하여 길찾기 알고리즘을 시도해보았다. 

 

하지만, 길을 가는 비용이 모두 동일하다 라는 조건이 성립해야만 이 BFS 알고리즘을 사용할 수 있다.

 

그렇다면, 이제 길에 각기 다른 비용이 들어간다고 해 보자.

어떤게 비용이 적게들까??

 

바로  1, 2, 3, 4, 5 이렇게 가는 방법이다. 왜냐면 5의 비용을 적기 때문! 

 

이렇게 가중치가 있을 경우 최단경로를 구할 수 있는 알고리즘이 다익스트라 알고리즘이다.

 

이제 다익스트라 알고리즘을 코드로 구현 해 보자.

 

우리가 눈으로 볼 때는 당연한 말이지만 알고리즘을 이해하려면 항상 컴퓨터적인 사고를 해야한다.

 

나머지 비용은 모른다. 오로지 내 앞에 연결된 Vertex까지의 비용을 알아내야 한다!

 

즉, 내가 연결된 Vertex의 모든 비용을 비교해서 최소 비용을 알고 있는다. (이게 어찌보면 예약의 개념)

 

그리고, 예약된 리스트에서 최소 비용을 가진 Vertex에 방문한다. 또 연결된 Vertex를 찾고 비용을 계산한다.

 

하지만 한가지 빠진 내용이 있는데..바로 비용을 누적시켜야 한다. 그 이유는?

 

 

내가 1번에서 계산을 하고 2번으로 갔다고 가정해보자. 

내 앞에 연결된 아이는 비용이 5 밖에 들지 않는다. 그러면 5의 비용을 가질까? 아니다.

1에서 3까지 가는 비용이 12라고 가정을 한다면, 오히려 더 높은 비용이 발생하는 문제가 생긴다.

 

즉 내가 예약을 할때, 그 대상의 위치는 이전 위치를 누적시킨 값이 된다.

그래서 1,2,3을 가는 방법은 15의 비용이 들고 1,3을 가는 방법은 12의 비용이 든다.

 

결국 3은 최소 비용을 가질것이고 3으로 이동한다가 된다.

 

이러한 점을 이용해서 코드를 구현하면 다음과 같다!