Djikstra 알고리즘을 활용한 최단거리 탐색

소개글

Djikstra 알고리즘을 활용한 최단거리 탐색에 대한 보고서 자료입니다.

목차

1. Introduction
2. Overall system class design
3. Data structures
4. Algorithm specification
5. Discussion and Conclusion

본문내용

NT > dist[C]+dist[C,E])
E
3
A
13
update
C
D
(MAXINT > dist[C]+dist[C,D])1
7
array index(vertex)
0(A)
1(B)
2(C)
3(D)
4(E)
dist
0
3
1
8
14
s
TRUE
FALSE
TRUE
FALSE
FALSE
방문하지 않은 목록 중 가장 작은 distance를 갖는 vertex 방문 후 path update
array index(vertex)
0(A)
1(B)
2(C)
3(D)
4(E)
dist
0
3
1
8
13
s
TRUE
TRUE
TRUE
FALSE
FALSE
update(dist[E] > dist[B]+dist[B,E])
10
3
13
1
7
array index(vertex)
0(A)
1(B)
2(C)
3(D)
4(E)
dist
0
3
1
8
11
s
TRUE
TRUE
TRUE
TRUE
FALSE
방문하지 않은 목록 중 가장 작은 distance를 갖는 vertex 방문 후 path update
update(dist[E] > dist[B]+dist[D,E])
10
3
13 3
1
array index(vertex)
0(A)
1(B)
2(C)
3(D)
4(E)
dist
0
3
1
8
11
s
TRUE
TRUE
TRUE
TRUE
TRUE
7
마지막으로 방문하지 않은 노드방문 후 update 후 최단경로 탐색 종료
-Adjacency List
Linked List * array[5]
A
B
C
D
E
head
head
head
head
A
B
C
D
E
D
D
C
E
E
E
C
B
A
A
C
B
head
Adjacency List
-Minimum path
Dijkstra algorith을 통해 최단경로의 database를 구현했다면, 최단경로를 저장할 array가 필요하다. 각각의 source vertex시작 모든 destination vertex에 도달하는 최단경로가 필요하므로 2D-array가 필요하다.
Minimum path의 정보는 그래프 탐색을 통해 최단경로를 찾는 과정에서 같이 수행한다.(update가 되는 부분에 min path를 저장한다)
Minimum path 2D-array
source vertex
destination vertex
0 [A]
1 [B]
2 [C]
3 [D]
4 [E]
A
A
A
C
D
B
A
A
C
B
...
...
...
...
...
...
각각의 source vertex에서 destination vertex의 경로참조는 destination vertex으로의 경로를 역순으로 참조한다.
가령, source vertex가 A이고 destination vertex가 E이라고 하면, 다음처럼 최단경로를 참조한다.
destination vertex C -> 4[E] / D -> 3[D] / C -> 2[C] / A <- source vertex
=> A - C - D
D
C
A
B
E
-Link shutdown
cost = MAXINT
D
B
C
A
E
Shutdown을 시행할 edge의 cost를 MAXINT로 변경한 후 다시 Dijkstra algorith을 수행한다.
4. Algorithm specification
다시 destination vertex를 시작으로 source vertex의 최단경로 역순참조를 진행하면서 bandwidth 할당
destination vertex를 시작으로 source vertex의 최단경로 역순참조
요청 보류
종 료
할당 가능 flag를 set
Vertex와 array의 index를 mapping
역순 참조를 진행하면서 vertex사이의 edge에 bandwidth를 할당할 수 있는가?
시 작
시 작
Link fail의 edge 구간에 할당된 서비스가 존재하는가?
Link fail의 edge 구간에 할당된 서비스 반환
Link fail의 edge 구간의 cost를 MAXINT로 설정
Djikstra algorithm 수행하여 최단경로 database 갱신
반환된 서비스를 재할당하기 위한
Request 요청이 성공하였는가?
종 료
-Request -Link fail
No
Yes
No
Yes
No
Yes
-Eos -reassignment
더 이상 처리할 서비스 요청이 없는가?
시 작
종 료
탐색된 최단경로에 할당이 가능한가?
최단경로가 탐색이 가능한가?
요청에 대한 다음 최단경로 탐색
낮은 대역폭의 요청을 우선처리순위로 결정
보류된 목록이 존재 하는가?
보류된 요청을
할당하기 위한
Request 요청이 성공하였는가?
종 료
요청 보류
보류된 요청이 존재하는가?
해당 서비스 반환
시 작
요청 폐기
요청 보류
요청 처리
No
Yes
No
No
Yes
Yes
No
Yes
No
Yes
No
Yes
5. Discussion and Conclusion
이번 과제에서는 최단경로를 탐색하는 알고리즘 중 하나인 Dijkstra 알고리즘을 통해 라우터의 동작을 구현하였다. inputfile로부터 라우터 정보를 읽어들여 Adjacency list를 만들고 이 list를 통해 Dijkstra 알고리즘을 완성했다. 이 Database를 바탕으로 대역폭 할당을 담당하는 Request 서비스를 종료하는 EOS, Link의 오류의이벤트인 Link fail을 구현하였다. 이번 학기 프로젝트 중에서 가장 복잡했었던 만큼, class 디자인과 여러 이벤트를 처리하는 과정에서 미흡한 부분이 많았던 것 같다. 물론 이런 점들이 프로그래밍의 실력을 늘려준다는 건 알고 있고, 또한 프로젝트를 진행하는 과정에서 몸으로 직접 느꼈다. 평소에 설계 단계를 소홀히하고 직접 부딪혀가면서 프로그램을 짜던 습관이 좋지 못하다는 걸 여실히 느꼈다. 요구하는 기능이 점점 추가될수록 고려하지못한 부분에서 함수의 중복설계를 하게 되는 속된말로 밑빠진 독에 물 붇기 식의 코딩을 하게되었다. 물론, 이런 점들을 중간단계에서 인지하고 고쳐나가려는 노력을 했지만 설계단계에서부터 조금 더 체계적인 설계를 했었다면 어땠을까 하는 생각이 이번 프로젝트에서 가장 크게 느꼈던 부분이다. 이번 프로젝트에서 얻은 깨달음이 앞으로 프로그래밍을 하는데 있어서 중요하게 작용될 듯 싶다.

키워드

Djikstra ,   알고리즘,   활용한 최단거리 탐색,   Djikstra 알고리즘을 활용한 최단거리 탐색