最短路径问题.txt

用C语言实现的学生管理代码

#include<stdio.h>
#include<stdlib.h>
#define MVNum 100//最大顶点数
#define Maxint 100000

enum  boolean{FALSE,TRUE};

typedef  char VertexType;
typedef int Adjmatrix;
typedef struct
{VertexType  vexs[MVNum];//顶点数组
 Adjmatrix arcs[MVNum][MVNum];//领接矩阵
}MGraph  *G;

int D1[MVNum],P1[MVNum];
int D[MVNum][MVNum],P[MVNum][MVNum];

#include"save.c"
#include"dijkstra.c"
#include"floyd.c"

void main()
{  MGraph  *G;
  int n,v,e,w,k;
  int xz=1;
  G=(MGraph *)malloc(sizeof(MGraph));
  printf("输入图形中顶点个数和边数n,e: ");
 scanf ("%d,%d",&n,&e);
  CreateMGraph(G,n,e);//建立图的存储结构
  while(xz!=0) 
  {
   printf("******求城市之间的最短路径******\n");
   printf("=================================\n");
   printf("1.求一个城市到所有城市的最短路径\n");
   printf("2.求任意两个城市之间的最短路径\n"); 
   printf("==================================\n");
   printf("请选择：1或2，选择0退出\n");
   scanf("%d",&xz);
   if(xz==2)
   {
       Floyd(G,n);//调用费洛伊德算法
       printf("输入起点和终点:v,w:");
       scanf("%d,%d",&v,&w);
       k=P[v][w];
       if(k==0)
       printf("顶点%d到%d无路径！\n",v,w);
       else
    {
        printf("从顶点%d到%d的最短路径是：%d",v,w,v);
        while(k!=w)
  {
          printf( "->%d",k);
          k=P[k][w];
  }
       printf("->%d",w);
       printf("路径长度：%d\n",D[v][w]);
   }
   }
   else
     if(xz==1)
  {
     printf("求单源路径，输入源点");
     scanf("%d",&v);
     Dijkstra(G,v,n);//调用迪杰斯特拉算法
  }

     printf("结束求最短路径，再见！\n");
  }
}

 


void  Floyd (MGraph *G,int n)
{  int i,j,k;
 for(i=0;i<=n;i++)
 for(j=0;j<=n;j++)
 {
   if(G->arcs[i][j]!=Maxint)
     P[i][j]=j;
      else
        P[i][j]=0;
      D[i][j]=G->arcs[i][j];
 }
    for(k=0;k<=n;k++)
 {
 for(i=0;i<=n;i++)
     for(j=0;j<=n;j++)
  {
   if (D[i][k]+D[k][j]<D[i][j])
   {
    D[i][j]=D[i][k]+D[k][j];
          P[i][j]=P[i][k];
          printf("dij=%d,pij=%d|n",D[i][i],P[i][j]);
   }
  }
 }
} 

 

 

 

 

void  Dijkstra( MGraph *G,int v1,int n)
{
   int D2[MVNum],P2[MVNum];
   int v,i,w,min;
   enum boolean S[MVNum];
   for(v=1;v<=n;v++);
   {S[v]=FALSE;
     D2[v]=G->arcs[v1][v];
   if(D2[v]<Maxint)
     P2[v]=v1;
   else
   P2[v]=0;
   }
  for(i=2;i<n;i++)
  {
    min=Maxint;
  for(w=1;w<=n;w++)
       if(!S[w]&&D2[w]<min)
    {
    v=w;
        min=D2[w];
    }
       S[v]=TRUE;
       for(w=1;w<=n;w++)
       if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w]))
    {
  D2[w]=D2[v]+G->arcs[v][w];
  P2[w]=v;
 }
       printf("路径长度   路径\n");
       for(i=1;i<=n;i++);
    { 
  printf("%5d",D2[i]);
        printf("%5d",i);
  v=P2[i];
    while(v!=0)
       printf("<-%d",v);
       v=P2[v];
    }
      printf("\n");
  }
}

 


void CreateMGraph(MGraph * G,int n,int e)//采 用邻接矩阵构造有向图G，n,e分别表示顶点数和边数
{
 int i,j,k,w;
    for(i=0;i<=n;i++)
    G->vexs[i]=(char)i;
    for(i=0;i<=n;i++)
 for(j=0;i<=n;i++)
    G->arcs[i][j]=Maxint;   //初始化邻接矩阵

 
   printf("输入%d条边地i,j及w:\n",e);
   for(k=1;k<=e;k++)
   { 
  scanf("%d,%d,%d",&i,&j,&w);
  G->arcs[i][j]=w;
   }
 printf("有向图的存储结构建立完毕!\n");
}