다익스트라 알고리즘 (2) 썸네일형 리스트형 CH5 : Network Layer Control Plane (1) * 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. * Routing 목적지까지 데이터를 보낼 때 어떤 경로를 거쳐 보내야 할지 정하는 것은 매우 중요하다. 실제로 src에서 dst까지 다양한 경로가 존재할 수 있기 때문에 최적의 path를 찾기 위한 방법을 제시해주는 것이 Routing Algorithm이다. 이때 라우터와 그 간의 링크들은 그래프에서 vertex와 edge로 표현될 수 있다. 이렇게 각 링크의 트래픽양이 다르고 어떤 경로를 통해 데이터를 보냈을 때 가장 적은 트래픽의 영향을 받으며 보낼 수 있을까? 알고리즘 파트에서 배웠던 그래프에서의 최단거리 알고리즘들이 떠오른다. (벨만포드, 다익스트라, 플로이드..... 다익스트라(Dijkstra) 알고리즘 다익스트라 (Dijkstra) 다익스트라는 어떤 그래프에서 특정노드에서 특정노드까지의 최단거리를 구할때 쓰는 알고리즘이다. 바로 예시를 들어보자. 다음과 같은 그래프가 있다. 1번 노드에서 2번 노드로 가기위한 최소거리를 구할때 우리는 모든 엣지의 크기를 동시에 살피며 눈대중으로 찾을 것이다. 코딩을해서 찾는거보다 그냥 머리로찾는게 빠를거다. 그러나 노드의 개수가 많아지고 엣지의 개수가 많아지면 문제가 생긴다. 때문에 우리는 최단거리를 찾는 알고리즘을 통해 노드간의 최단거리를 찾아야 하는데 이에 대표적으로 사용되는 알고리즘이 바로 다익스트라이다. 설명 다익스트라는 BFS의 기본 틀에 우선순위 큐를 접목하여 구현할 수 있다. BFS에 대한 설명은 여기(링크)에 있당! 1번 노드에서 각 노드로 가기위한 최소.. 이전 1 다음
