注册 登录
编程论坛 数据结构与算法

数据结构迪杰斯特拉算法,帮忙看下

书生小白 发布于 2012-01-01 22:10, 604 次点击
1.以下是迪杰斯特拉算法(词汇有一点改动),其中有两个函数不明白是什么意思,求解释,其中一个是Member(G->vex[i],S)另外一个是AddTail(&S,G->vex[k]);
2.作业就被这个算法给难住了,求解释,帮帮忙啊,如果有那两个函数代码,麻烦贴出来,供打架研究一下,谢谢了
  我在线等啊,求解释。。。。。。
void DJS(Graph *G,int v0,int dsit[MAX],Vertex path[MAX])
//G是邻接矩阵存储图
//v0为当前愿点,path[][]保存当前最短路径,dist为最短路径长度
//path[]中存放顶点i当前的最短路径。dist[]中存放当前的最短路径长度
//
{
    Vertex S; //S为顶点相同类型,S是找到路径最短的集合
    for (i=0;i<G->vexnum;i++)
    {
        InitList(&path[i]);//初始化
        dist[i]=G->Arc[v0][i];
        if (dist[i]<INFINITE)
        {
            AddTail(&path[i],G->vex[v0]);//AddTail()是尾添加函数
            AddTail(&path[i],G->vex[i]);
        }
    }
    InitList(&S);
    AddTail(&S,G->);
    for (t=1;t<G->vexnum;t++)//求v0到其余剩下顶点的最短路径
    {
        min=INFINITE;
        for (i=0;i<G->vexnum;i++)
        {
            if (!Member(G->vex[i],S) && dist[i]<min)//求下一条路径
            {
                k=i;
                min=dist[i];
            }
        }
        AddTail(&S,G->vex[k]);
        for (i=0;i<G->vexnum;i++)       //修正dist[i],
        {
            if(!Member(G->vex[i],S) && G->Arc[k][i].adj!=INFINITE
                && (dist[k]+G->Arc[k][i].adj<dist[i]))
            {
                dist[i]=dist[k]+G->Arc[k][i].adj;
                path[i]=path[k];
                AddTail(&path[i],G->vex[i]);
            }
        }
    }
}
1 回复
#2
书生小白2012-01-01 22:42
没人啊,自己顶下。。
1