迪杰斯特拉算法实现错误
编写的时候思想如下:二维矩阵存储两个节点之间边的权重,若不相连接为INF
首先从节点1开始,1和其他节点之间的权重,若不为INF则可能是最短路径,进行判断
判断:1 存储到目标点的值为0,此时看目标点是否为0,如果目标点是1则不许修改,否则修改成到当前点的值加上当前点到目标点的值
2 判断到目标点的值是否小于当前点的值加上当前点到目标点的值,如果是,修改成当前点的值加上当前点到目标点的值
一轮循环之后取最短的路径并将其在buf中的对应位置1表示已取得最小值,然后将下一边轮换的节点换成此值然后进行下一轮循环
当buf中所有值都为1时跳出循环,返回数组,数组中的值是从节点1到其他节点的最短路径,在main之中打印出来
代码如下:#include <stdio.h>
#define INF 1000
int * Dijiesitela(int []);
int get_min(int * tar,int * exi,int n);
int all(int * n);
int main(void)
{
int * DJ_return;
int dis [] = {
{0,1,INF,INF,INF,INF,7,INF},
{1,0,2,INF,INF,INF,INF,9},
{INF,2,0,3,INF,INF,INF,INF},
{INF,INF,3,0,4,INF,INF,INF},
{INF,INF,INF,4,0,5,INF,10},
{INF,INF,INF,INF,5,0,6,INF},
{7,INF,INF,INF,INF,6,0,8},
{INF,9,INF,INF,10,INF,8,0}
};
DJ_return = Dijiesitela(dis);
for(int i = 0;i<8;i++)
printf("%d\r\n",*DJ_return);
return 0;
}
int * Dijiesitela(int dir[])
{
int buf_return = {0};
int buf = {0};
buf = 1;
int i,j,k;
i = j = k =0;
while(1)
{
for(i=0;i<8;i++)
{
if(dir!=INF) //!=INF的话才可能成最短路径
{
if((!buf_return&&i!=0) || (buf_return+dir<buf_return)) //如果buf_return==0，之前没有路径直接给值
buf_return = buf_return+dir;
}
}
j = get_min(buf_return,buf,8);
k = j-1;
buf = 1;
if(all(buf))
break;
}
return buf_return;
}
int get_min(int * tar,int * exi,int n)
{
int i;
int min = 0;
int i_return;
for(i=0;i<n;i++)
{
if(!exi)
{
if(!min)
{
if(tar)
{
min = tar;
i_return = i;
}
}
else if(tar<min)
{
min = tar;
i_return = i;
}
}
}
return i_return+1;
}
int all(int * n)
{
int counter;
for(int i =0;i<8;i++)
{
if(*(n+i) == 1)
counter ++;
}
if(counter == 8)
return 1;
return 0;
}
编译通过,但是卡死了,条件限制debug不了,求帮忙看看哪里出了问题 忘记设置赏金了,最佳答案联系我我重发一个帖子给
赏金10
页:
[1]