迪杰斯特拉算法实现错误

被萌妹所蒙昧

编写的时候思想如下:
二维矩阵存储两个节点之间边的权重,若不相连接为INF
首先从节点1开始,1和其他节点之间的权重,若不为INF则可能是最短路径,进行判断
判断:1 存储到目标点的值为0,此时看目标点是否为0,如果目标点是1则不许修改,否则修改成到当前点的值加上当前点到目标点的值
        2 判断到目标点的值是否小于当前点的值加上当前点到目标点的值,如果是,修改成当前点的值加上当前点到目标点的值
一轮循环之后取最短的路径并将其在buf中的对应位置1表示已取得最小值,然后将下一边轮换的节点换成此值然后进行下一轮循环
当buf中所有值都为1时跳出循环,返回数组,数组中的值是从节点1到其他节点的最短路径,在main之中打印出来
代码如下:

1. #include <stdio.h>
   
2. #define INF 1000
   
3. 
   
4. int * Dijiesitela(int [][8]);
   
5. int get_min(int * tar,int * exi,int n);
   
6. int all(int * n);
   
7. int main(void)
   
8. {
   
9.     int * DJ_return;
   
10. 
    
11.     int dis [][8] =    {
    
12.                             {0,1,INF,INF,INF,INF,7,INF},
    
13.                             {1,0,2,INF,INF,INF,INF,9},
    
14.                             {INF,2,0,3,INF,INF,INF,INF},
    
15.                             {INF,INF,3,0,4,INF,INF,INF},
    
16.                             {INF,INF,INF,4,0,5,INF,10},
    
17.                             {INF,INF,INF,INF,5,0,6,INF},
    
18.                             {7,INF,INF,INF,INF,6,0,8},
    
19.                             {INF,9,INF,INF,10,INF,8,0}
    
20.                         };
    
21. 
    
22.     DJ_return = Dijiesitela(dis);
    
23. 
    
24.     for(int i = 0;i<8;i++)
    
25.         printf("%d\r\n",*DJ_return);
    
26. 
    
27.     return 0;
    
28. }
    
29. 
    
30. int * Dijiesitela(int dir[][8])
    
31. {
    
32.     int buf_return[8] = {0};
    
33.     int buf[8] = {0};
    
34.     buf [0] = 1;
    
35.     int i,j,k;
    
36.     i = j = k =0;
    
37.     while(1)
    
38.     {
    
39.         for(i=0;i<8;i++)
    
40.         {
    
41.             if(dir[k][i]!=INF)                                      //!=INF的话才可能成最短路径
    
42.             {
    
43.                 if((!buf_return[i]&&i!=0) || (buf_return[k]+dir[k][i]<buf_return[i]))                            //如果buf_return[i]==0，之前没有路径直接给值
    
44.                     buf_return[i] = buf_return[k]+dir[k][i];
    
45.             }
    
46.         }
    
47.         j = get_min(buf_return,buf,8);
    
48.         k = j-1;
    
49.         buf[k] = 1;
    
50. 
    
51.         if(all(buf))
    
52.             break;
    
53.     }
    
54. 
    
55.     return buf_return;
    
56. }
    
57. 
    
58. int get_min(int * tar,int * exi,int n)
    
59. {
    
60.     int i;
    
61.     int min = 0;
    
62.     int i_return;
    
63.     for(i=0;i<n;i++)
    
64.     {
    
65.         if(!exi[i])
    
66.         {
    
67.             if(!min)
    
68.                {
    
69.                 if(tar[i])
    
70.                 {
    
71.                     min = tar[i];
    
72.                     i_return = i;
    
73.                 }
    
74.                }
    
75.         else if(tar[i]<min)
    
76.         {
    
77.             min = tar[i];
    
78.             i_return = i;
    
79.         }
    
80.         }
    
81.     }
    
82.     return i_return+1;
    
83. }
    
84. 
    
85. int all(int * n)
    
86. {
    
87.     int counter;
    
88. 
    
89.     for(int i =0;i<8;i++)
    
90.     {
    
91.         if(*(n+i) == 1)
    
92.             counter ++;
    
93.     }
    
94.     if(counter == 8)
    
95.         return 1;
    
96. 
    
97.     return 0;
    
98. }
    

复制代码

编译通过,但是卡死了,条件限制debug不了,求帮忙看看哪里出了问题

被萌妹所蒙昧

忘记设置赏金了,最佳答案联系我我重发一个帖子给
赏金10