최단경로를 구하는 Dijkstra의 알고리즘 구현

소개글

c언어로 최단경로를 구하는 Dijkstra의 알고리즘을 구현 한 것입니다.
코드 및 분석까지 완벽한 보고서 입니다.
코드 포함 되어있습니다.

목차

없음

본문내용

▣ 문제 분석 : 최단경로를 구하는 Dijkstra의 알고리즘 구현
▶ 최단 경로를 구하는 Dijkstra의 알고리즘을 구현해 본다. 파일에 그래프의 인접 행렬을 미리 저장해 둔 후, 프로그램을 실행하면 파일에 저장되어있는 그래프의 인접 행렬이 출력 된다. 각 에지에 대한 가중치와 출발점, 도착점은 직접 입력받아 최단경로를 구하게 된다. 인접 행렬의 정의는 다음과 같다.
정점 집합 V(G)={V1 , V2 , ... , Vn}인 그래프 G=(V(G),E(G))의 인접 행렬은 그래프를 구성하는 각 정점들 간의 인접 여부를 n*n의 2차원 배열로 표현한 것이다. 2차원 배열 A(i,j)에서 연결 (Vi , Vj)가 E(G)에 속하면 A(i , j) = 1이 되고, E(G)에 속하지 않으면 A(i,j) = 0 이 된다.

인접 행렬의 문제점은 다음과 같다.
인접 행렬로는 n(n-1)개의 edge를 표현할 수 있다. 그러나 실제로는 그래프내의 edge 수는 이보다 훨씬 적기 때문에 대부분의 행렬 원소는 0의 값을 가진다. 따라서 완전 그래프처럼 edge가 많은 경우를 제외하고는 상당량의 기억 장소가 낭비되는 문제가 있다. 이러한 문제를 해결하기 위해서는 인접 리스트를 사용한다.

<중 략>

▣ 결과 분석 및 토의 (이해나)
첫 번째 읽은 파일의 예를 들어보자. 정점의 개수는 8개, 에지의 개수는 10개이다. 에지(0,1), (0,2), (1,3), (1,4), (2,5), (2,6), (3,7), (4,7), (5,7), (6,7) 의 에지가 있으므로 가중치를 각 에지에 대하여 입력하면 프로그램은 distance배열을 업데이트 시키며 시작점부터 도착점까지의 최단거리를 알려준다.
Dijkstra 최단경로 문제는 두 지점 사이의 가장 짧은 경로를 찾는 문제로서 가중 그래프에서는 구성하는 구간들의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제이다. 예를 들면 지도상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제인데 각 구간에서 걸리는 시간을 가중치에 비유할 수 있으며, 어떤 점 u에서 v로 이동하는 거리도 가중치에 비유할 수 있다. Dijkstra 알고리즘은 인터넷 라우팅에서 사용되는 OSPF(open shortest path first)방식의 프로토콜은 Dijkstra 알고리즘이 실제 현상에서 사용되는 좋은 사례이다.

참고 자료

없음