Dijkstra Algorithm

Dijkstra Algorithm

 

동적 혹은, Adaptive즉, 적응적 Routing기법 알고리즘등으로 불리는 유명한 알고리즘에 대해 공부했던 내용을 Review한다.또한 Dijkstra’s Algorithm에 대해서도 언급하고 있다.
 

Picture 1. example of Dijkstra’s Algorithm

 

Source node를 1이라고 하고, Destination Node를 8이라고 할 때, 인접배열을 위한 table이 위처럼 작성될 수가 있다.

처음 1의 입장에서 2와 6은 인접해 있기에 그 거리를 기록할 수가 있다. 즉 알수 있다고 보는 것이다. 이에 반해서, 나머지 node는 보이지 않는다. 아득한 거리로 보자는 것이다.

역시 만약 2번 path를 타기로 결정했다면, 2에서 볼 때, 1,3,4를 제외하고는 아득한 거리가 되버린다. 바로 이런식의 패턴이 Dijkstra’s Algorithm의 concept이다.

 

Dijkstra’s Alogorithm에 대한 글을 읽다가 보면, 최단거리를 기록해 가다가 좀 더 작은 값이 나오게 되면 이를 갱신한다라는 말이 많다.

이 의미는 다음과 같다.

 

4에서 거리가 결정되는 것은 5와 7이다. 이때, 다른 path인 6을 타는 경로에서 7이 또 결정될수가 있다. 즉, 4를 타는 path에서의 최단거리의 총합 이때의 기준은 그 시점에서의 최종 node이다. 즉 여기선 4이다. 헌데, 최종node가 7인 path를 타려하는 것이다.

최종이 7이되면, 최단거리는 5가 된다. 헌데, 6번을 탔을 경우 그 값이 9가되어 최단거리는 갱신되지 못할 것이다. 즉 node 7까지 왔을 때 물론, 이때는 최단거리 경로를 탔을 것이다.

그 값이 5가 된다. 그리고 이놈은 fixed된다. 이것이 영구 값이 되는 것이다.

 

순간 순간 시점에서의 즉, 최종node를 바꿔가면서 실제의 최종node를 찾아가되 각각의 step에서, 최단거리 값을 기록해 가는 것이다.그러면서, 최단거리값이 제일 작은 것이 계속적으로 setting되다가, 최종적으로는 영구값이 될 것이다.

여기서 우리는 이것이 Dynamic Routing이 되지 못함을 또한 알수가 있다. 

 

 Picture 2. example of Dijkstra’s subnet?^^

 

따라서 이제, 1->2->4->7->8 path가 이 subnet에서 from 1 to 8의 최단거리 경로가 됨을 알 수가 있다.

Dijkstra’s Alogorithm은 이처럼 순간수간 중간최종node에서의 최단거리 값의 결정에 대한 조사가 이루어지는 것이다.

4번에서 7로 가는 것말고도 5로 갈수도 있었을 것이다 하지만, 이럴경우

2+1+3+4 > 2+1+2+4가 되어 결국 node 8의 최단거리 값은 수정되지 않고 fixed된다.

 

이런 subnet은 traffic이나, 최소 전송 Delay time등을 고려하지 못하는 것이다. 

   

Picture 3. point and time to select

 

Node 1에서 Node 12로 가는 경로에서의 최소거리 Routing을 하고싶다고 하자.

 

먼저 위에서 선택의 시점이 몇번 온다고 생각할 수가 있을까?

6번이다.

Node 1에서 선택해야 한다.

Node 2에서 선택해야 한다.

Node 3에서 선택해야 한다.

Node 4에서 선택해야 한다.

Node 8에서 선택해야 한다.

Node 7에서 선택해야 한다.

 

혹여, Node 2,3에서나, Node 7에서의 선택을 왜 해야하냐고 반문할 수가 있겠으나,

그건 아마도 최적의 경로상에서의 선택이 아니기 때문일것이다.

하지만, 그건은 답을 알고 풀이과정을 그것에 맞추는 것이다.

 

Dijkstra’s Alogorithm으로 문제를 푼다고 할 때, 설사 그림상 빙 돌아가는 듯 하여도

반드시 거리가 조사되어야 한다. 빙 돌아가는 것이 오히려 최단거리 최적루트가 될수도 있기때문이다. 심지어 다음의 경우도 있다. 

Node 4에서의 최단거리의 합이 결정났다고 했을 때, Node 4에서는 3과 8의 루트를 가질수가 있겠으나, 이때 거리가 +8로써 같기에, 이 경우는 단순히 선택의 차원이 넘어서서

최단거리 계산반영에 까지 이어지게 된다. 즉 일단 내려갔다가 다시 4로 돌아와서의 최단거리 합이 계산되어서 이것이 더 크다고 판명이 날때까지인 것이다.

 

중요한 것은 반드시 인접 노드가 2개 이상일 때, 그 거리의 값이 동일했다면, 단순히 조사를 하여 선택할수 있는 것이 아니라, 설사 결과적으로는 최적루트상의 root가 아니었다고 하여도, 그 노드로 가는 path를 검사하여 다시 돌아왔을 시점에서의 최단거리 값을 구하여야 한다. 여기서 그 값이 설정된 값보다 크다고 판명날 때 이쪽 path가 아님을 인지하는 것이다. 물론 이런 세세한 부분은 프로그램의 방향에 따라 다소 다를수 있겠다 싶다.

 

머리속의 내용을 설명하기가 쉽진않다.

거리를 조사한다와 조사한 거리를 더하여 크기를 비교한다의 개념을 난 구분해서 사용했음을 알려드린다.

 

그렇다면, 결국 최소거리는 몇일까?

32이다.  금방 알 수 있을 것이다.