Shortest Path Algorithm

소개글

본 프로그램은 어떤 vertex들이 서로 연결되어있는 그래프에서 두 지점을 선택해 한쪽 지점에서 다른 한쪽 지점으로 가는 최단 경로, 길이를 구하는 프로그램이다. vertex는 모두 연결되어 있지만 그 모두가 양방향으로 연결된 것은 아니다. 이 그래프를 프로그램화 하면 matrix가 가장 적합하다. 때문에 그래프를 matrix화 하고 그것으로 원하는 최단 경로 및 길이를 구하는 것이다.
최단 경로 및 길이를 방법에서 우리는 Dynamic programming 이라는 개념을 도입한다. Dynamaic programming은 문제를 플어나감에 있어서 어떤 일정한 연관성을 가질 때 적합하다. 예를 들면 recursive 형태의 문제 풀이법에 유용하게 쓰인다.
본 문제에서는 최단 경로 및 길이를 구하는 것이므로 어떤 지점에서 다른 지점으로 갈 때, 편의상 a에서 b로 나타나겠다. a에서 b로 가는 경로와 길이를 찾게 될 때 vertex를 거쳐가는 경우와 그렇지 않은 경우들을 비교해가며 구하게 된다. 한가지 경우를 먼저 정해 놓고 그것에 대한 결과값을 저장해 놓고 다시 이 값을 이용하여 다른 경우에 대해 비교하여 더 최적의 경우를 저장하게 된다. 이런 형태의 동적인 방법을 사용한 프로그램이다.

컴파일 실행환경

GNU Gcc / Debian Linux

참고 자료

없음