我的狄斯奎诺算法出问题了

我的狄斯奎诺算法出问题了

kukumh
酷酷我的心
等级:

发表于：2007-12-05 17:25:28 楼主

#include <iostream.h>
#define MAX_FLOT_NUM 3.14E38

struct adj_list
{
int v_num;//邻接顶点的编号
float len;//邻接顶点与该顶点的距离
struct adj_list *next;//下一个邻接顶点
};
typedef struct adj_list NODE;

/************************************************
*dijkstra()算法说明：
*p[]是存放顶点i到源点的最短路径上的前方顶点的编号；
*u是源顶点变量；
*d[i]表示顶点i到源顶点的距离；
*node[]存放边的长度；
*n为顶点个数。
*************************************************/
void dijkstra(NODE node[],int n,int u,float d[],int p[])
{
float temp;
int i,j,t;
bool *s=new bool[n];//s[i]为真，表示顶点i在s中，否则不在；
NODE *pnode;

for(i=0;i <n;i++)
{
d[i]=MAX_FLOT_NUM;
s[i]=false;
p[i]=-1;
}

if(!(pnode=node[u].next))
{
return;
}

while(pnode)
{
d[pnode->v_num]=pnode->len;
p[pnode->v_num]=u;
pnode=pnode->next;
}

d[u]=0;
s[u]=true;

for(i=1;i <n;i++)
{
temp=MAX_FLOT_NUM;
t=u;

for(j=0;j <n;j++)
{
if((!s[j]) && d[j] <temp)
{
t=j;
temp=d[j];
}
}

if(t==u)
break;
s[t]=true;
pnode=node[t].next;

while(pnode)
{
if((!s[pnode->v_num]) && d[pnode->v_num]>d[t]+pnode->len)
{
d[pnode->v_num]=d[t]+pnode->len;
p[pnode->v_num]=t;
}
pnode=pnode->next;
}

delete s;
}
}

void main()
{
NODE node[10];

NODE *node14; node14->v_num=4; node14->len=3; node14->next=NULL;
NODE *node13; node13->v_num=3; node13->len=2; node13->next=node14;
NODE *node12; node12->v_num=2; node12->len=4; node12->next=node13;
node[0].v_num=1;
node[0].len=0;
node[0].next=node12;

NODE *node26; node26->v_num=6; node26->len=9; node26->next=NULL;
NODE *node25; node25->v_num=5; node25->len=10; node25->next=node26;
node[1].v_num=2;
node[1].len=0;
node[1].next=node25;

NODE *node37; node37->v_num=6; node37->len=7; node37->next=NULL;
NODE *node36; node36->v_num=6; node36->len=7; node36->next=node37;
NODE *node35; node35->v_num=5; node35->len=6; node35->next=node36;
node[2].v_num=3;
node[2].len=0;
node[2].next=node35;

NODE *node47; node47->v_num=7; node47->len=8; node47->next=NULL;
NODE *node46; node46->v_num=6; node46->len=10; node46->next=node47;
node[3].v_num=4;
node[3].len=0;
node[3].next=node46;

NODE *node59; node59->v_num=9; node59->len=8; node59->next=NULL;
NODE *node58; node58->v_num=8; node58->len=4; node58->next=node59;
node[4].v_num=5;
node[4].len=0;
node[4].next=node58;

NODE *node69; node69->v_num=9; node69->len=6; node69->next=NULL;
NODE *node68; node68->v_num=8; node68->len=9; node68->next=node69;
node[5].v_num=6;
node[5].len=0;
node[5].next=node68;

NODE *node79; node79->v_num=9; node79->len=4; node79->next=NULL;
NODE *node78; node78->v_num=8; node78->len=5; node78->next=node79;
node[6].v_num=7;
node[6].len=0;
node[6].next=node78;

NODE *node810; node810->v_num=10; node810->len=8; node810->next=NULL;
node[7].v_num=8;
node[7].len=0;
node[7].next=node810;

NODE *node910; node910->v_num=10; node910->len=4; node910->next=NULL;
node[8].v_num=9;
node[8].len=0;
node[8].next=node910;

node[9].v_num=10;
node[9].len=0;

float d[10];
int p[10];
dijkstra(node,10,1,d,p);

for(int i=0;i <10;i++)
{
cout < < p[i] < < "\t";
}
}

问题点数：20 回复次数：4 修改删除举报引用回复