sy4.c

最短路径的分析

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

#define MAX 32767
#define MAXVEX  100

struct vertex
{
	int num;
	char data;   /*顶点以字符表示*/
};

typedef struct graph
{
	struct vertex vexs[MAXVEX];
	int edges[MAXVEX][MAXVEX];
}adjmax;

int dist[MAXVEX],shortest[MAXVEX][MAXVEX];
adjmax adj;
int n,e;

//建立有向图
void creatgraph()
{
	int i,j,k,w;
	char b,t;
	printf("\n输入顶点数：");
	scanf("%d",&n);
	printf("\n输入边数(e)：");
	scanf("%d",&e);
	printf("输入顶点信息（以一个字符表示）：");
	for(i=1;i<=n;i++)
	{
		getchar();
		printf("输入第%d个顶点的信息：",i);
		scanf("%c",&adj.vexs[i].data);
		adj.vexs[i].num=i;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			adj.edges[i][j]=MAX;
	for(i=1;i<=n;i++)
		adj.edges[i][i]=0;
	printf("\n*****************输入边信息：******************\n");
	for(k=1;k<=e;k++)
	{
		getchar();
		printf("输入第%d条边的信息（起点，终点，权值）",k);
		scanf("%c,%c,%d",&b,&t,&w);
		i=1;
		while(i<=n && adj.vexs[i].data!=b) i++;
		if(i>n) 
		{
			printf("输入的起点不存在!\n");
		}

	
	   j=1;
	   while(j<=n && adj.vexs[j].data!=t) j++;
	   if(j>n)
	   {
		 printf("输入的终点不存在！\n");
	   }
	  if(i<=n && j<=n)
	   adj.edges[i][j]=w;
	  else k--;
	}
}



void print()		//打印
{
	int i,j,k;
	i=1;
	while(i<=n)
	{
		printf("\n第%d个顶点",adj.vexs[i].num);
		printf("%c\n",adj.vexs[i].data);
		i=i+1;
	}
	for(k=1;k<=n;k++)
		for(j=1;j<=n;j++)
		{
			if(adj.edges[k][j]!=32767)
				printf("\n起点:%d,终点%d,权值%d\n",k,j,adj.edges[k][j]);
		}
}

void shortpath_floyd()//求最短路径的弗洛伊德
{
	int path[MAXVEX][MAXVEX];
	int i,j,k;
	for (i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			shortest[i][j]=adj.edges[i][j];
			path[i][j]=0;
		}
	for (k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(shortest[i][j]>(shortest[i][k]+shortest[k][j]))
				{
					shortest[i][j]=shortest[i][k]+shortest[k][j];
				    path[i][j]=k;
				}
     printf("\nFloyd算法运行成功！\n");
}



void printpath_Floyd()//打印最短路径
{
	int i,j;
	printf("\n源点到各点之间的最短路径\n");
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(i!=j)
			{
				if(shortest[i][j]!=MAX)
				
					printf("%c-->%c:%d\t   ",adj.vexs[i].data,adj.vexs[j].data,shortest[i][j]);
				
				else  
					printf("%c-->%c:NO WAY!\t  ",adj.vexs[i].data,adj.vexs[j].data);
			}
		}
	}
}



void shortpath_dijkstra(int v0)   //Dijkstra算法
{
	int s[MAXVEX];
	int mindis,dis,i,j,u;
	for(i=1;i<=n;i++)
	{
		dist[i]=MAX;
		dist[i]=adj.edges[v0][i];
		s[i]=0;
	}
	s[v0]=1;
	for(i=1;i<=n;i++)
	{
		mindis=MAX;
		for(j=1;j<=n;j++)
			if(s[j]==0 && dist[j]<mindis)
			{
				u=j;
				mindis=dist[j];
			}
			s[u]=1;
			for(j=1;j<=n;j++)
				if(s[j]==0)
				{
					dis=dist[u]+adj.edges[u][j];
					dist[j]=(dist[j]<dis)?dist[j]:dis;
				}	
		}
	printf("\nDijkstra算法运行成功！\n");
}


void printpath_dijkstra(v0)//打印最短路径
{
	int i;
	printf("\n从源点%c到其它各点的最短路径：\n",adj.vexs[v0].data);
	for(i=1;i<=n;i++)
	{
		printf("%c-->%c:",adj.vexs[v0].data,adj.vexs[i].data);
		if (dist[i]==MAX)
			printf("NO WAY\n");
		else 
			printf("%5d\n",dist[i]);
	}
}



void main()//主程序
{

	int f=1;
	int cycle=1;
	char c;
	while(cycle){	
		printf("\n 功能选择：\n");
		printf("\n1.创建图 ");
		printf("\n2.打印图 ");
		printf("\n3.求最短路径FLOYD ");
		printf("\n4.打印短路径FLOYD ");
		printf("\n5.求短路径DIJKSTRRA  ");
		printf("\n6.打印短路径DIJKSTRRA  ");
		printf("\n7.退出");
		printf("\n\n请选择");
		scanf("%c",&c);
		if(c!='7')
		{
			switch(c){
			case'1':creatgraph();break;
			case'2':print();break;
			case'3':shortpath_floyd();break;
			case'4':printpath_Floyd();break;
			case'5':printf("\n请输入起点序号\n");
				scanf("%d",&f);
				shortpath_dijkstra(f);
				break;
			case'6':printpath_dijkstra(f);break;
			default:
				break;
			}
		}
		else cycle=0;
	}
	
}