习题4-求最短路径.c

数据结构各章实验源代码； 数据结构实验源代码

#include "datastru.h"
#include <stdio.h>
#include <malloc.h>
#define MAX  10000

MGRAPH create_mgraph(){
/*建立有向图的邻接矩阵结构*/
int i, j, k, h;
 MGRAPH  mg;

  mg.kind = 3;
  printf("\n\n输入顶点数和边数(用逗号隔开) : ");
  scanf("%d,%d", &i,&j);
  mg.vexnum = i;                                /*存放顶点数在mg.vexnum中 */
  mg.arcnum = j;                                /*存放边点数在mg.arcnum中*/
  fflush(stdin);
  for(i = 0; i < mg.vexnum; i++)
     { printf("输入顶点 %d 的值 : ",i + 1);     /*输入顶点的值*/
       scanf("%d", &mg.vexs[i]);
       fflush(stdin);}
  for(i = 0; i < mg.vexnum; i++)                /*邻接矩阵初始化*/
     for(j = 0; j < mg.vexnum; j++)
	mg.arcs[i][j] = MAX;
  for(k = 1; k <= mg.arcnum; k++)
    { printf("输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): ",k);
      scanf("%d,%d",&i,&j);                     /*输入弧的起始顶点和终止顶点*/
      fflush(stdin);
      while(i < 1 || i > mg.vexnum || j < 1 || j > mg.vexnum)
	{ printf("输入错，重新输入: ");
	  scanf("%d,%d", &i, &j);}
	  printf("输入此边权值 : ");                /*输入弧上之权值*/
	  scanf("%d", &h);
	  mg.arcs[i - 1][j - 1] = h;}
  return mg;
}

main()
{
	MGRAPH mg;
	int cost[MAXLEN][MAXLEN];
	int path[MAXLEN], s[MAXLEN];
	int dist[MAXLEN];
	int i, j, n, v0, min, u;

	printf("\n求有向图单源点最短路径\n");
	mg = create_mgraph();                    /*建立有向图的邻接矩阵结构*/
	printf("\n\n起始顶点为 : ");             /*有向图中顶点的编号从1编起*/
	scanf("%d", &v0);
	v0 --;
	n = mg.vexnum;
	for(i = 0; i < n; i++)                   /*cost矩阵初始化*/
	  {for(j = 0; j < n; j++)
		  cost[i][j] = mg.arcs[i][j];
		  cost[i][i] = 0;}
	for(i = 0; i < n; i++)              
		{dist[i] = cost[v0][i];              /*dist数组初始化*/
		 if(dist[i] < MAX && dist[i] > 0)    /*path数组初始化*/
			path[i] = v0;}
	for(i = 0; i < n; i++)                   /*s数组初始化*/
		s[i] = 0;
	s[v0] = 1;
	for(i = 0; i < n; i++)                   /*按最短路径递增算法计算*/
	   {	min = MAX ;
		u = v0;
		for(j = 0; j < n; j++)
			if(s[j] == 0 && dist[j] < min)
			  {min = dist[j];
			   u = j;}
		s[u] = 1;                                 /*u顶点是求得最短路径的顶点编号*/
		for(j = 0; j < n; j++)
			if(s[j] == 0 && dist[u] + cost[u][j] < dist[j])/*调整dist*/
			  {dist[j] = dist[u] + cost[u][j];
			path[j] = u;}                         /*path记录了路径经过的顶点*/
	   }
	for(i = 0; i < n; i++)                        /*打印结果*/
	   if(s[i] == 1)
		  {u = i;
		   while(u != v0)
			  {printf("%d <- " , u + 1);
			   u = path[u];}
		   printf("%d ", u + 1);
		   printf("  d = %d\n", dist[i]);         /*有路径*/
		  }
	   else
		  printf("%d <- %d  d= MAX\n ", i + 1, v0 + 1);/*无路径*/
printf("\n\n");
}