读书人

急最短路径算法有关问题。

发布时间: 2012-01-12 22:11:58 作者: rapoo

急!!!最短路径算法问题。。。。
以下是本人参考别人写的最短路径问题的主要程序部分,但用VC6.0运行之后只有前3个节点到源点的最短路径长度正确,其它均为32767。请各位高手帮忙看下,改正一下,本人万分感谢!!!!

==========================================================================
typedef struct
{
int length; //最短路径长度
int pre; //前一个节点
}path;

int cost[N][N];//邻接矩阵数组
path dist[N];//最短路径数组

void BestPath(int m)
{
int i,u,min;

//初始化已求得最短路径节点数组
for(i=0;i <N;i++)
{
dist[i].length=cost[m][i];
if(dist[i].length!=32767) //以32767代表为不可达
dist[i].pre=m;
else
dist[i].pre=-1; //-1代表为空
}

cost[m][m]=1; //赋值为1表示将其加入已求得到源点最短路径集合S

for(;;)
{
u=-1;
min=32767;

//比较到源点路径长度,求出节点
for(i=0;i <N;i++)
{
if(cost[i][i]==0&&dist[i].length <min)
{
u=i;
min=dist[i].length;
}
}

if(u=-1)
{
break;
}

cost[u][u]=1;

//更新其余节点到源点的最短路径值
for(i=0;i <N;i++)
{
if(cost[i][i]==0&&dist[i].length> dist[u].length+cost[u][i])
{
dist[i].length=dist[u].length+cost[u][i];
dist[i].pre=u;
}
}
}
}
==========================================================================

[解决办法]
没看懂,讲下思路好吗

读书人网 >VC/MFC

热点推荐