[알고리즘] 정비소 문제 - Bellman Ford Algorithm

Q. Efficiently solve this problem for the following input. What algorithm should you use? Give the step - by - step descripion of the arrays D[0..6] and P[0..6]. Write the recursive algorithm 'void path (int P, int k)' to print out the final path. Write the final answer.

• Input
  120  (최대 거리)
  5  (정비소 개수)
  80  30  30  60  40  20  (거리)
  5  10  4  12  8  (정비 시간)

Input 값을 그림으로 표현

	０	1	2	3	4	5	6
T[최소비용]	０	5	10	9 (14 , 9)	21 (21 , 22)	17(17 , 29)	9 (9 , 21 , 17)
P(부모노드)	-1	0	0	1	3	3	3

※T[N+1] = 0 T[0]=0

• output 
  9       (최소 정비 시간)
  2       (방문 정비소 갯수)
  1   3   (방문 정비소 번호)
• Bellman Ford Algorithm
  
  

void path (int *p, int k) {
	if (k > 0)
    	{
            path(P,P[k]);
            printf("%d",K);
        }
}