sy7_5.c

数据结构实验与学习指导

#include "stdio.h"
#include "conio.h"
#include "string.h"
#define VEX_NUM 20
#define VERTEX_MAX 20   /*最大顶点数*/
#define MAXINT  20000  /*无路径的顶点在矩阵中取值,不可为int类型所表示的最大值，否则在程序中和min相加会造成溢出为负数,得到错误结果*/
typedef char Vextype[3];  /*顶点类型*/
typedef struct 
{
    Vextype vexs[VERTEX_MAX];   /*顶点信息*/
    int arcs[VERTEX_MAX][VERTEX_MAX];       /*邻接矩阵存储 */
    int vexnum,arcnum;    /*顶点数、边数*/
} MGraph;
int n,m;        /*实际顶点数、边数*/
void creat_MGraph(MGraph *g)    /*创建有向网络的邻接矩阵*/
{
    int i,j,k;      
    int w;
    printf("请输入顶点数和边数:");    /*输入顶点数n和边数m*/
    scanf("%d,%d",&n,&m);
    g->vexnum=n;
    g->arcnum=m; 
    printf("请输入顶点信息:");  /*输入顶点信息，如V0,V1等*/
    for (i=0;i<n;i++) 
    {
     scanf("%s",g->vexs[i]);  
     }
    for (i=0;i<n;i++)        /*初始化邻接矩阵*/
      for (j=0;j<n;j++)
        g->arcs[i][j]=MAXINT;
    printf("请输入两个顶点间的边和权值(i,j,w)\n");
    for (k=0;k<m;k++)        /*根据弧的顶点对邻接矩阵进行赋值*/
    {
        scanf("%d,%d,%d",&i,&j,&w);
        g->arcs[i][j]=w;
    }
    printf("创建成功!\n");
     for (i=0;i<n;i++)        /*输出邻接矩阵*/
      { for (j=0;j<n;j++)
        printf("%d  ",g->arcs[i][j]);
        printf("\n");
       }
}
/*===========Dijkstra算法===========*/
void  Dijkstra(MGraph Gn,int v0,int path[],int dist[])
/*求有向图Gn的v0顶点到其余顶点v的最短路径,path[v]是v0到v的最短路径上的前驱顶点,
dist[v]是路径长度*/
{  int i,j;
   int v,w,min;
   int s[VEX_NUM]; /*s数组用于标记已经找到最短路径的顶点,为1找到,为0未找到*/
   for(v=0;v<n;v++)  /*初始化s、dist、path*/
   { s[v]=0;
     dist[v]=Gn.arcs[v0][v];
     if(dist[v]<MAXINT)
        path[v]=v0;
     else  path[v]=-1;
    }
  dist[v0]=0;s[v0]=1;   /*V0为源点*/
  for(i=1;i<n;i++)  /*循环求v0到顶点v的最短路径，并将v并入S集合*/
  { min=MAXINT ;
    for(w=0;w<n;w++)
     if(!s[w]&&dist[w]<min)   /*从所有顶点中找到为加入S集的且离v0最近的顶点vw,先记录下vw的相关信息，再更新其他顶点的dist[j]*/
    {     
     v=w;
     min=dist[w];       
    s[v]=1 ;  /*顶点v并入S集合*/
    for(j=0;j<n;j++)                   /*更新当前最短路径*/
     if(!s[j]&&(min+Gn.arcs[v][j]<dist[j]))
     {
       dist[j]=min+Gn.arcs[v][j] ;
       path[j]=v ;
      } /*内层if*/
    } /*外层if*/
  }  /*for*/
}  /*  Dijkstra */
void  putpath(MGraph g,int v0,int p[],int d[])  
{  /*输出v0到其余顶点的最短路径及距离*/
  int i;
  int next;
  for(i=0;i<n;i++)
   if(p[i]!=-1 && i!=v0)
    {
      printf("%s<--",g.vexs[i]);
      next=p[i];
      while(next!=v0)
       {
         printf("%s<--",g.vexs[next]);
         next=p[next];
       }
      printf("%s:%d\n",g.vexs[v0],d[i]);
     }
   else  if(p[i]==-1 && i!=v0)
     printf("%s<--%s:没有路径存在\n",g.vexs[i],g.vexs[v0]);
   }  /*  path  */
void main()
{
  int i,v0,fg;
  Vextype  vinfo;
  int path[VEX_NUM],dist[VEX_NUM];
  MGraph g;
  creat_MGraph(&g);
  do
  {
    printf("0:退出  1:dijkstra算法\n");  /*操作界面*/
    printf("请选择操作0~1: ");
    scanf("%d",&fg);
    switch(fg)
    {
     case 0:break; /*退出*/
     case 1:printf("输入起始顶点v0:");
          getchar();
          gets(vinfo);
          for(i=0;i<VEX_NUM;i++)   /*将源点转化为序号*/
          if (strcmp(vinfo,g.vexs[i])==0)  
            v0=i;
          Dijkstra(g,v0,path,dist);
          putpath(g,v0,path,dist);
          break;
     default:printf("输入错误，请重新选择!\n");
          break;
   }
 } while (fg!=0);
}