储存结构，结构体的定义：（权值w用于表示两点间路径的花费）
typedef int Status;
typedef struct ENode//图的邻接表定义
{
int adjVex;//任意顶点u相邻接的顶点
int w;//边的权值
struct ENode* nextArc;//指向下一个边结点
}ENode;
typedef struct LGraph
{
int n;//图的当前顶点数
int e;//图的当前边数
ENode **a;//指向一维指针数组
}LGraph;
迪杰斯特拉算法：
int Choose(int *d, int *s,int n) //每次选择一个为加入数组s【】的具有最小权值的结点
{
int i,minpos,min;
min=INFTY;
minpos=-;
for(i=;i<n;i++)
{
if(d[i]<min&&!s[i])
{
min=d[i];
minpos=i;
}
}
return minpos;
}
Status Dijkstra(int v,int *d,int *path,LGraph *lg)//迪杰斯特拉算法求路径
{
int i,j,k,w;
ENode *p;
p=lg->a[v];//工作指针
int *s; if(v<||v>lg->n-)
{
return ERROR;
} s=(int*)malloc(sizeof(int)*lg->n);
for(i=;i<lg->n ;i++)
{
s[i]=;
path[i]=-;
d[i]=INFTY;
} while(p)//初始化
{
d[p->adjVex ]=p->w ;
if(p->adjVex!=v&&d[p->adjVex ]<INFTY)
{
path[p->adjVex ]=v;
}
p=p->nextArc ;
} //对各个数组初始化
s[v]=;
d[v]=;
for(i=;i<lg->n ;i++)
{ k=Choose(d,s,lg->n );
if(k==-)
{
continue;
} //判断是否选择了有效结点
s[k]=;
p=lg->a[k];
if(p==NULL)
{
continue ;
}
while(p)
{
if(!s[p->adjVex ]&&d[k]+p->w <d[p->adjVex ])//更新d和path
{
d[p->adjVex ]=d[k]+p->w ;
path[p->adjVex ]=k;
}
p=p->nextArc ;
}
}
return OK;
}
void fun(LGraph *lg)//此函数用于输出路径
{
int v,u;
printf("please input u and v:\n");
scanf("%d %d",&u,&v);
int d[lg->n];
int path[lg->n];
Dijkstra(u,d,path,lg);
printf("path: ");
if(path[v]==-)
{
printf("无\n");
return ;
}
while (path[v]!=-)
{
printf("%d <--- ",v);
v=path[v];
}
printf("%d\n",u);
}