인생자취

1. 들어가기어떤 A지점에서 다른 B지점으로 이동하는 경로는 다양할 수 있다. 이는 네트워크에서도 마찬가지로 적용되는 부분이다. 연결 경로가 다양하게 존재할 수 있다. 경로가 다양하게 존재할 수 있는 가운데, 주목해야할 것은 가장 짧은 경로의 경우다. 이를 최단 경로라고 부른다. 최단 경로 문제는 다양한 경로 중 적은 비용으로 빠르게 이동하는 경로를 찾는 문제다. 이번 글에서는 최단 경로의 개념 및 이와 관련된 다익스트라 알고리즘에 대해 알아보고, 예제 문제를 살펴볼 것이다. 2. 최단경로어떤 가중치가 부여된 방향 그래프가 있다고 하자. 가중치가 부여된 그래프의 비용은 가중치를 계산하여 최단거리를 결정할 수 있다. 이때 가중치를 비용이라고 한다면 경로의 합이 가장 적은 경우가 최단 거리가 된다. 그리고 ..