수다닷컴

질문 제목 : 다익스트라 알고리즘 경로 출력다익스트라 알고리즘 경로에 관한 소스를 짯는데 경로를 출력하는 부분에서 많이 막히네요 ㅠ
길을 찾고 가장 가중치가 작은 경로를 찾는거 까지 했는데 그 이후에 그 경로를 출력하는 부분이;;;질문 내용 : 뭐 간단하게 소스로 올리겠습니다.

void searchpath()
{
//입력: (없음)
//기능: graph에 존재하는 각 vertex를 shortestpath()의 파라메터로 이용하여 해당 vertex에서 다른 vertex로의 shortestpath를 찾는다
//출력: (없음)
//calling: shortestpath(), printpath()
//called: makegraph()
//기타: 자기 자신에 대한 path이거나 다른 vertex로의 path가 존재 하지 않는 경우에는 shortestpath()를 수행하지 않음

int i,j;
for(i=0;itotalvertex;i++){//vertex 수만큼 반복
printf(\n\nsource vertex: %d\n, i);
fprintf(out, \nsource vertex: %d\n, i);
shortestpath(i);//가장 짧은 경로 찾음
for(j=0;jtotalvertex;j++){
if(i!=j){
printpath(j);//경로 출력
printf(\n);
}
}
}
}
void printpath(int vertex)
{
//입력: (없음)
//기능: path[]에 저장된 값을 이용하여 찾아진 shortestpath를 출력한다.
//calling: printpath()
//called: searchpath()
//기타: 재귀함수로 구현한다
//(base case: 해당 vertex로의 path가 존재하지 않는 경우.)

if(!path[vertex])
printf(%d -, path[vertex]);

}
void shortestpath(int vertex)
{
//입력: vertex - source vertex for finding shortest path
//기능: 입력받은 vertex에서 다른 모든 vertex로의 shortest path를 찾는다.
//출력: (없음)
//calling: initarray(), choose()
//called: searchpath()
//기타:
//수행하기 전에 initarray()를 호출하여 found[], distance[], path[]를 초기화
//source vertex 자신은 이미 찾아진 vertex이므로 해당하지 않으며 마지막
//vertex는 자동으로 추가되므로 totalvertex - 2 만큼 반복하며 s의 원소를 찾게 된다.
int i,u,w;
initarray(vertex);//배열을 초기화 found[i]는 false로, distance[i] = cost[vertex][i]로
for(i=0;imax_vertex-2;i++){
u = choose();//시작 정점 v로 부터 최소거리를 갖는 정점 u를 반환
found[u] = true;//true로 초기화
for(w=0;wmax_vertex;w++){
if(!found[w]){
if(distance[u] + cost[u][w] distance[w])
distance[w] = distance[u] + cost[u][w];
}
}
}
}

여기서 printpath 함수가 어떤 행동을 해야 할지 감이 안잡히네요 ㅠ

대략의 설명이라도 부탁드립니다....

신청하기