다익스트라 알고리즘(Dijkstra’s Algorithm)

다익스트라 알고리즘(Dijkstra’s Algorithm)

지난 1956년 에드거 W 다익스트라가 고안한 것으로 최단 경로를 탐색하는 알고리즘이다. 통신간 최단 경로를 결정하기 위해 경로 길이를 계산하는 것으로 이 알고리즘의 가장 큰 장점은 불필요한 경로를 생략할 수 있게 해줬다는 것이다. 
(Graph에서 최단 경로를 계산)

설명 아래 링크 잘나오네요
http://thrillfighter.tistory.com/235
http://thrillfighter.tistory.com/63
위의 링크 이미지를 이용해서 설명하겠습니다.

조건은 그래프의 가중치가 음이 없어야 하고 출발 지점으로 부터의 전체 비용의 최소가 얼마가 되는지 계산 됩니다.

즉, 1번 원에서 8번 원까지 갈때 최소 가중치 즉 최소 비용을 계산하는 알고리즘 입니다.
2번에서 8번으로 갈때 비용은 2에서 출발해서 새로 계산해봐야 합니다.
탐색 할때 가중치에 따라 탐색하는 순서가 있고(비용이 작은곳 부터) 낮은 곳으로 비용의 갱신이 일어납니다.

1의 비용은 0로 설정 : 출발이므로

아직 계산 안한 node들의 전체 비용은 임의의 큰값 설정

node가 연결안된경우 임의의 큰값 설정

loop 노드의 수만큼 루프{

확인 안한 노두 중 모든 노드 검사하여 비용 중 가장 작은 비용의 노드를 알아냄 minNode

각 노드들 모두 순회하면서 minNode의 비용 + 순회하는 node의 node간 비용 < 순회하는 node 전체 비용 (조건을 만족하면 : 순회하는 node 전체 비용 = minNode의 비용 + 순회하는 node의 node간 비용 을 넣음)

}

설명----------------------------------

1에서 출발하면 아래와 같습니다. 

step 0)

아직 계산 안한 node들의 전체 비용은 임의의 큰값 설정

value[] = {M,M,M,M,M,M,M,M}

1의 비용은 0로 설정

value[0] = 0

value[] = {0,M,M,M,M,M,M,M}

node가 연결안된경우 임의의 큰값 설정

step 1)

확인 안한 노두 중 모든 노드 검사하여 비용 중 가장 작은 비용의 노드를 알아냄 minNode

value[] 내용중 처음이니까 1번 노드가 최소 값이 됩니다. minNode = 1

step 2)

각 노드들 모두 순회하면서 minNode의 비용 + 순회하는 node의 node간 비용 < 순회하는 node 전체 비용

0+{비용(1->2):1} < {비용(2):M} => 조건 만족 비용(2)<=1 

0+{비용(1->3):2} < {비용(3):M} => 조건 만족 비용(3)<=2

...

0+{비용(1->8):M} < {비용(8):M} => 조건 미만족

루프 돌고나면 아래와 같이 됩니다.

value[] = {0,1,2,M,7,M,M,M}

step 3)

확인 안한 노두 중 모든 노드 검사하여 비용 중 가장 작은 비용의 노드를 알아냄 minNode

value[] = {0,1,2,M,7,M,M,M} 여기에서 1번 노드는 앞에서 확인했으므로 minNode = 2가됨

설명이 어렵네요. 그림으로 정리하였습니다.

------------------------------------------------