Dijkstra 알고리즘 경로 출력
글쓴이: 야구볼까축구볼까@Naver / 작성시간: 화, 2017/04/04 - 11:10오후
다음과 같이 Dijkstra 알고리즘을 c언어로 구현했는데 최단 경로를 출력하는 부분이 아리까리 하네요...
재귀함수 써서 구현했었는데 재귀함수 쓰지 않고 최단경로를 출력하는 방법이 있나요?
입력 : input.txt (파일첨부)
출력 : 1 3 6 8
#include <stdio.h> #define N 100 #define INF 9999 int a[N + 1][N + 1]; // 가중치값이 저장된 배열 int visit[N + 1]; // 정점 방문 여부 int dist[N + 1]; // 시작점에서 정점까지의 최단거리 int start, end; int n, m; // input 값 sample // 첫번째 라인에는 정점의 개수, 그리고 시작 정점, 도착 정점이 입력 // 두번째 라인에는 정점별 간선의 입력받을 가중치의 개수(m)가 입력된다. // 세번째 라인부터는 정점별 간선의 입력받을 가중치가 m번이 들어온다. void dijkstra() { int i, j; int min; int v; dist[1] = 0; // 시작점의 거리 0 for (i = 1; i <= n; i++) // n개의 정점을 모두 방문할 때 까지 반복 { min = INF; for (j = 1; j <= n; j++) { if (visit[j] == 0 && min > dist[j]) // 방문하지 않은 정점 중 토탈 가중치(dist[j])가 가장 작은 정점 선택 { min = dist[j]; v = j; } } visit[v] = 1; // 선택한 정점을 방문한 것으로 체크 // 시작점(1)에서 방문한 정점(v)을 통해 다른 정점(j)까지의 거리가 짧아지는지 계산하여 누적된값 저장 for (j = 1; j <= n; j++) if (dist[j] > dist[v] + a[v][j]) dist[j] = dist[v] + a[v][j]; } } int main(void) { int i, j; int from, to; int w; freopen("input2.txt", "r", stdin); setbuf(stdout, NULL); scanf("%d %d %d", &n, &start, &end); scanf("%d", &m); // 각 정점으로 가는 간선의 가중치를 무한대로 초기화한다.(최소값을 구하기위해) for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) if (i != j) a[i][j] = INF; for (i = 1; i <= m; i++) // 정점에서 정점으로 가는 간선의 가중치가 입력 { scanf("%d %d %d", &from, &to, &w); a[from][to] = w; } for (i = 1; i <= n; i++) dist[i] = INF; dijkstra(); printf("%d \n", dist[end]); return 0; }
File attachments:
첨부 | 파일 크기 |
---|---|
input.txt | 163바이트 |
Forums:
기능 구현은 아니지만. 이거도 참고해보세요.
http://www.devpia.com/MAEUL/Contents/Detail.aspx?BoardID=50&MAEULNO=20&no=953286&ref=953286&page=2
----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.
매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.
각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com
댓글 달기