实现迪杰斯特拉的最短单源路径算法

/*实现迪杰斯特拉的最短单源路径算法*/

//此算法可以实现查找单元最短路径，并打印出各点的最短路径值及路径上各点

#include<stdio.h></stdio.h>
#include<stdlib.h></stdlib.h>
#include<malloc.h></malloc.h>

#define INFINITY 1000


typedef int VRType;                 
typedef char InfoType;
typedef int VertexType;              
typedef enum{DG,DN,AG,AN} GraphKind;     //定义图类型

typedef struct arccell{
     VRType adj;
     InfoType *info;
}ArcCell;

typedef struct graph{
     VertexType *vexs;
     ArcCell **arcs;
     int vexnum;
     int arcnum;
     GraphKind kind;
}Graph;

typedef struct result{
     int **PathMatrix;
     int *ShortPathTable;
}Result;

void CreateDN(Graph *dn,Result *r)             //根据输入产生图
{
    int i,j,m,k,x,y,a,b,e,n;
    char c;
    
    printf("请输入图的节点数\n");
    scanf("%d",&n);

    dn->vexnum=n;
    dn->kind=DN;
    dn->vexs=(VertexType *)malloc(sizeof(VertexType)*n);
    ArcCell **temp=(ArcCell **)malloc(sizeof(ArcCell *)*n);
    for(i=0;iarcs=temp;
    
    int **tmp=(int **)malloc(sizeof(int *)*n);
    for(i=0;iPathMatrix=tmp;
    
    r->ShortPathTable=(int *)malloc(sizeof(int)*n);
           
    printf("请依次输入各节点的值\n");

    for(i=0;ivexs[i]);
    }

    for(i=0;iarcs[i][j].adj=INFINITY;
           dn->arcs[i][j].info=NULL;
        }
    }

    printf("边是否有附加信息(Y/N)？\n");
    c=getch();
    putch(c);
    printf("\n");
    if(c=='Y'||c=='y')
         m=1;
      else m=0;

    printf("请输入边数\n");
    scanf("%d",&k);
    dn->arcnum=k;

    printf("请按先头节点后尾节点然后权的顺序输入边\n");

    for(i=0;ivexs[a])
               break;

        printf("尾节点");
        scanf("%d",&y);
        for(b=0;bvexs[b])
               break;

        printf("权值");
        scanf("%d",&e);

        dn->arcs[a][b].adj=e;

        if(m){
           printf("请输入附加信息\n");
           scanf("%s",&dn->arcs[a][b].info);
        }
    }
}

void ShortPath_DIJ(Graph *g,int v0,Result *r)
{
    int v,w,i,min,j;
    int *final;
    final=(int *)malloc(sizeof(int)*g->vexnum);

    for(v=0;vvexnum;v++)
    {
        final[v]=0;
        r->ShortPathTable[v]=g->arcs[v0][v].adj;

        for(w=0;wvexnum;w++)
            r->PathMatrix[v][w]=-1;

        if(r->ShortPathTable[v]PathMatrix[v][0]=v0;
            r->PathMatrix[v][1]=v;
        }
    }

    r->ShortPathTable[v0]=0;
    final[v0]=1;

    for(i=1;ivexnum;i++)
    {
        min=INFINITY;
        
        for(w=0;wvexnum;w++)
        {
           if(!final[w])
               if(r->ShortPathTable[w]ShortPathTable[w];
               }
        }

        final[v]=1;

        for(w=0;wvexnum;w++)
        {
            if(!final[w]&&(min+g->arcs[v][w].adjShortPathTable[w])){
                r->ShortPathTable[w]=min+g->arcs[v][w].adj;
                for(j=0;jvexnum;j++)
                {
                    r->PathMatrix[w][j]=r->PathMatrix[v][j];          //此为打印路径的关键步骤
                    if(r->PathMatrix[w][j]==-1){
                        r->PathMatrix[w][j]=w;
                        break;
                    }    
                }    
            }
        }
    }
}

void Print(Graph *dn,int a,Result *r)
{
    int i,j;

    printf("%d到各顶点的最短路径如下\n",a);

    for(i=0;ivexnum;i++)
    {
        printf("%d到%d的最短路径长%d,\n",a,dn->vexs[i],r->ShortPathTable[i]);
        printf("路径是\n");

        for(j=0;jvexnum;j++)
        {
            if(r->PathMatrix[i][j]>-1)
               printf("%2d",dn->vexs[r->PathMatrix[i][j]]);
        }

        printf("\n");
    }
}

main()
{
    int a,v,n;
    Graph dn;
    Result r;

    CreateDN(&dn,&r);    
    printf("寻找哪个定点的最小路径？\n");
    scanf("%d",&a);
    for(v=0;v

评论

1 楼 simohayha 2007-04-14  

啥都没有，只有代码，不知道贴出来有什么意义？