/*狄斯奎诺算法(dijkstra)<邻接表> */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 0x3f3f3f3f
#define NN 100000
struct stu
{
int v_num; /* 邻接表编号*/
float len; /* 边长*/
struct stu *next ;
};
/*n表示节点个数,u-->表示源节点*/
stu gong[NN] ;
void Dijkstra(int n,int u,float dis[],int p[])
{
int i,j,t;
float temp;
bool *ss = ( bool *)malloc(sizeof(bool)) ; //逐步的放进ss{}集合中
stu * pstu;
for(i=0;i<n;i++) //init(dis,p)
{
dis[i]=maxn;
p[i]=-1; //表示前一个节点为root;
ss[i]=false; //flase-->表示没有在ss集合中
}
if(!(pstu=gong[u].next)) //表示只有自己一个节点
return ;
while(pstu)
{
dis[pstu->v_num] = pstu->len ;
p[pstu->v_num] = u ; //表示该顶点
pstu=pstu->next;
}
dis[u]=0;
ss[u]=true; //表示这个顶点在ss集合中
for(i=0;i<n;i++)
{
temp=maxn;
t=u;
for(j=0;j<n;j++)
{
if(!ss[j]&&temp>dis[j])
{
temp=dis[j];
t=j;
}
}
if(t==u) break; //说明没有最路!
ss[t]=true;
pstu=gong[t].next;
while(pstu)
{
if(!ss[pstu->v_num]&&dis[pstu->v_num]>dis[t]+pstu->len)
{
dis[pstu->v_num]=dis[t]+pstu->len;
ss[pstu->v_num]=true;
}
pstu=pstu->next;
}
}
free(ss);
}