Dijkstra 알고리즘 경로 출력

야구볼까축구볼까@Naver의 이미지

다음과 같이 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: 
첨부파일 크기
Plain text icon input.txt163바이트
shint의 이미지

----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.

매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.

각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.