소개글
다익스트라 알고리즘의 수행 방법을 쉽게 표기 한 내용입니다.
목차
Dijkstra?
Dijkstra - 변수
Dijkstra - 초기화
본문내용
Dijkstra?
가중치가 있는 그래프의 최단 경로를 구하는 알고리즘
출발 정점에서 시작하여 현재의 정점까지의 값과 인접한 정점의 가중치 합이 가장 작은 정점을 다음 정점으로 선택하고 그 경로를 최단 경로에 포함시킨다
이 과정을 모든 정점이 선택될 때까지 반복한다
시작점에 연결되어 있는 정점 사이의 거리를 구해서 최소값을 갖는 정점에 표시한다.
표시를 해둔 정점에 연결되어있는 각 정점까지의 거리를 구하고, 이 때 계산된 정점(표시되어 있지 않은) 사이의 거리 중에서 최소값을 갖는 정점에 표시한다.
이 과정을 모든 정점에 표시할 때까지 반복하면, 각 정점에서 얻을 수 있는 값이 곧 시작점에서의 최단거리를 뜻하게 된다.
#define N 8
#define M 9999
int a[N+1][N+1]={ {0,0,0,0,0,0,0,0,0},
{0,0,1,7,2,M,M,M,M},
{0,1,0,M,M,2,4,M,M},
{0,7,M,0,M,M,2,3,M},
{0,2,M,M,0,M,M,5,M},
{0,M,2,M,M,0,1,M,M},
{0,M,4,2,M,1,0,M,6},
{0,M,M,3,5,M,M,0,2},
{0,M,M,M,M,M,6,2,0}};
참고 자료
없음