图的最短路径

#include <stdio.h>
#include <string.h>
#define INFINITY 1000
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,UDG,UDN} Graphkind;
typedef struct ArcCell{
int adj;
char *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
char vexs[MAX_VERTEX_NUM][4];
AdjMatrix arcs;
int vexnum,arcnum;
Graphkind kind;
}MGraph;
int visited[MAX_VERTEX_NUM];
void CreateGraph(MGraph *G);
void CreateDG(MGraph *G);
void CreateDN(MGraph *G);
void CreateUDG(MGraph *G);
void CreateUDN(MGraph *G);
int LocateVex(MGraph *G,char v[4]);
void Girst_next_adj(MGraph *G,int i);
void dfs1(MGraph *G,int i);
void bfs1(MGraph *G,int i);
void shortesPath_DIJ(MGraph *G,int v0,int p[][MAX_VERTEX_NUM],int d[MAX_VERTEX_NUM]);
#define QUEUE_INIT_SIZE 100
#define QUEUEINCREMENT 10
typedef int QElemType;
typedef struct{
QElemType *elem;
int front;
int rear;
int queuesize;
int incrementsize;
}SqQueue;
void InitQueue_sq(SqQueue *Q,int n);
int QueueLength_Sq(SqQueue Q);
int DeQueue_Sq(SqQueue *Q,QElemType *e);
void incrementQueuesize(SqQueue *Q);
void EnQueue_Sq(SqQueue *Q,QElemType e);
int GetQueue_Sq(SqQueue Q,QElemType *e);
int QueueEmpty(SqQueue Q);
main(){
MGraph G;
int i,j;
char v[4];
int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM],d[MAX_VERTEX_NUM];
       CreateGraph(&G);
for(i=0;i<G.vexnum;++i)
{
    for(j=0;j<G.vexnum;++j)
     printf("%8d",G.arcs[i][j].adj);
    putchar('\n');
}
printf("输入深度优先搜索初始顶点Vi: ");
getchar();
scanf("%s",v);
i=LocateVex(&G,v);
dfs1(&G,i);
printf("\n输入出发广度优先搜索初始顶点: ");
getchar();
scanf("%s",v);
       i=LocateVex(&G,v);
bfs1(&G,v);
bfs1(&G,i);
if(G->kind==DN||G->kind=UDN)
{
    printf("\n输入查找第一邻接点的顶点： ");
    getchar();
    scanf("%s",v);
    i=LocateVex(&G,v);
    shortesPath_DIJ(&G,0,p,d);
}
}
int visited[MAX_VERTEX_NUM];
void dfs1(MGraph *G,int i)
{
int j;
printf("%5s",G->vexs[i]);
visited[i]=1;
for(j=0;j<G->vexnum;j++)
    if(i!=j&&G->arcs[i][j].adj!=INFINITY&&!visited[j])
     dfs1(G,j);
}
void bfs1(MGraph *G,int i)
{
int k,j;
SqQueue Q;
for(j=0;j<G->vexnum;j++)
    visited[j]=0;
InitQueue_Sq(&Q,G->vexnum);
printf("\n%5s",G->vexs[i]);
visited[i]=1;
EnQueue_Sq(&Q,i);
while(!QueueEmpty(Q))
{
    DeQueue_Sq(&Q,&k);
    for(j=0;j<G->vexnum;j++)
    {
     if(k!j&&G->arcs[k][j].adj!=INFINITY&&!visited[j])
     {
      printf("%5s",G->vexs[j]);
      visited[j]=1;
      EnQueue_Sq(&Q,j);
     }
    }
}
}
int LocateVex(MGraph *G,char v[4])
{
int i=0;
while(i<G->vexnum)
{
    if(strcmp(G->vexs[i],v)==0) return i;
            i++;
}
printf("\n输入的顶点不存在！");
return 0;
}
void CreateDG(MGraph *G)
{}
void CreateDN(MGraph *G)
{
int i,j,k,w;
char v1[4],v2[4];
printf("输入DN--vexnum,arcnum:");
scanf("%d%d",&G-<vexnum,&G->arcnum);
printf("输入vexs[i]:\n");
getchar();
for(i=0;i<G->vexnum;++i)
    gets(G->vexs[i]);
for(i=0;i<G->vexnum;++i)
        switch(k)
{
    case 0:G->kind=DG; break;
    case 1:G->kind=DN; break;
    case 2:G->kind=UDG; break;
    case 3:G->kind=UDN; break;
}
switch(G->kind)
{
case DG:CreateDG(G); break;
case DN:CreateDN(G); break;
case UDG:CreateUDG(G); break;
case UDN:CreateUDN(G); break;
}
printf("ok!\n");
}
void First_next_adj(MGraph *G,int i)
{
int j;
for(j=0;j<G->arcs[i][j].adj!=INFINITY)
    if(G->arcs[i][j].adj!=INFINITY)
       printf("%s\n",G->vexs[j]);
}

void shortesPath_DIJ(MGraph *G,int v0,intp[][MAX_VERTEX_NUM],int d[MAX_VERTEX_NUM]){
 int i,j,v,min,w,final[MAX_VERTEX_NUM],v1,w1;
 for(v=0;v<g->vexnum;++v){
    final[v]=0;
    d[v]=G->arcs[v0][v].adj;
    for(w=0;w<G->vexnum;++w)
     p[v][w]=0;
    if(d[v]<INFINITY){
     p[v][v0]=1;p[v][v]=1;
    }
 }
 printf("\nfinal[]:");
 for(v1=0;v1<G->vexnum;++v1)
    printf("%6d",final[v1]);
 printf("\n\n      d[]:     ");
 for(v1=0;v1<G->vexnum;++v1)
    printf("%6d",d[v1]);
 printf("\n\np[][]:\n");
 for(v1=0;v1<G->vexnum;++v1){
    for(w1=0;w1<G->vexnum;++w1)
     printf("%6d",p[v1][w1]);
    putchar('\n');
 }
 d[v0]=0;final[v0]=1;
 for(i=1;i<G->vexnum;++i){
    min=INFINITY;
    for(w=0;w<G->vexnum;++w)
     if(!final[w])
      if(d[w]<min){
       v=w;
       min=d[w];
      }
      final[v]=1;
      for(w=0;w<G->vexnum;++w)
       if(!final[w]&&(min+G->arcs[v][w].adj<d[w])){
        d[w]=min+G->arcs[v][w].adj;
        for(j=0;j<G->vexnum;++j)
         p[w][j]=p[v][j];
        q[w][w]=1;
       }
       printf("\nfinal[]:");
       for(v1=0;v1<G->vexnum;++v1)
        printf("%6d",final[v1];
       printf("\n\n      d[]:      ");
           for(v1=0;v1<G->vexnum;++v1)
        printf("%6d",d[v1]);
       printf("\n\np[][]:\n");
       for(v1=0;v1<G->vexnum;++v1){
        for(w1=0;w1<G->vexnum;++w1)
         printf"%6d",p[v1][w1]);
        putchar('\n');
       }
 }
}