鱼C论坛

 找回密码
 立即注册
查看: 2747|回复: 1

迪杰斯特拉算法实现错误

[复制链接]
发表于 2019-10-30 22:34:19 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

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

int * Dijiesitela(int [][8]);
int get_min(int * tar,int * exi,int n);
int all(int * n);
int main(void)
{
    int * DJ_return;

    int dis [][8] =    {
                            {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[][8])
{
    int buf_return[8] = {0};
    int buf[8] = {0};
    buf [0] = 1;
    int i,j,k;
    i = j = k =0;
    while(1)
    {
        for(i=0;i<8;i++)
        {
            if(dir[k][i]!=INF)                                      //!=INF的话才可能成最短路径
            {
                if((!buf_return[i]&&i!=0) || (buf_return[k]+dir[k][i]<buf_return[i]))                            //如果buf_return[i]==0,之前没有路径直接给值
                    buf_return[i] = buf_return[k]+dir[k][i];
            }
        }
        j = get_min(buf_return,buf,8);
        k = j-1;
        buf[k] = 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[i])
        {
            if(!min)
               {
                if(tar[i])
                {
                    min = tar[i];
                    i_return = i;
                }
               }
        else if(tar[i]<min)
        {
            min = tar[i];
            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不了,求帮忙看看哪里出了问题
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2019-10-30 22:35:17 | 显示全部楼层
忘记设置赏金了,最佳答案联系我我重发一个帖子给
赏金10
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 13:07

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表