zdlj.cpp

在所输入的图中找到任意两点间的最短路径并将路径以图的形式输出

#include <stdio.h>
#define MAX 9999
#define MAXVertex 100
#define N 7
typedef char VexType;
typedef int AdjType;

typedef struct
{
	int n;
	VexType vexs[MAXVertex];
	AdjType arcs[MAXVertex][MAXVertex];
}GraphMatrix;
                                    
typedef struct
{
    VexType vertex;
	AdjType length;
	int prevex;
}Path;

Path dist[N];

void init(GraphMatrix graph,Path dist[])
{
	int i;
	dist[0].length=0;         
	dist[0].prevex=0;
	dist[0].vertex=graph.vexs[0];

	graph.arcs[0][0]=1;

	for(i=1;i<graph.n;i++){
		dist[i].length=graph.arcs[0][i];
		dist[i].vertex=graph.vexs[i];
		if(dist[i].length!=MAX)
			dist[i].prevex=0;
		else dist[i].prevex=-1;
	}
}

void dijkstra(GraphMatrix graph,Path dist[])
{
	int i,j,minvex;
	AdjType min;
	init(graph,dist);
	for(i=1;i<graph.n;i++){
		min=MAX;
		minvex=0;
		for(j=1;j<graph.n;j++){
			if(graph.arcs[j][j]==0&&dist[j].length<min){
				min=dist[j].length;
				minvex=j;
			}
		}
			if(minvex==0)break;
			graph.arcs[minvex][minvex]=1;
			for(j=1;j<graph.n;j++){
				if(graph.arcs[j][j]==1) continue;
				if(dist[j].length>dist[minvex].length+graph.arcs[minvex][j]){
					dist[j].length=dist[minvex].length+graph.arcs[minvex][j];
					dist[j].prevex=minvex;
				}
			}
		}
}


void initgraph(GraphMatrix &graph,int n)
{
	char p;
	int i, j;
	int t,s,k;
	graph.n=n;
	for(i=0;i<graph.n;i++)
		for(j=0;j<graph.n;j++)
			graph.arcs[i][j]=(i==j?0:MAX);
		for(i=0;i<graph.n;i++)
		graph.vexs[i]='#';
		printf("请输入图中顶点的信息  若输入完毕,以0结束\n");
        for(i=0;i<graph.n+1;i++){
			scanf("%c",&p);
			if(p=='*')break;
				graph.vexs[i]=p;
			}
        printf("请输入图中弧的信息,输入形式:尾结点 头结点 权值   若输入完毕，以0 0 0结束\n");
		for(i=0;i<graph.n*graph.n;i++){
			scanf("%d%d%d",&t,&s,&k);
			if(t==0&&s==0&&k==0)break;
			graph.arcs[t-1][s-1]=k;
		}
		printf("所有节点为:");
		for(i=0;i<graph.n;i++){
			if(graph.vexs[i]!='#')
				printf("%4C",graph.vexs[i]);
		}
        printf("\n图的邻接矩阵如下\n");
        for(i=0;i<graph.n;i++){
			for(j=0;j<graph.n;j++){
				printf("%8d",graph.arcs[i][j]);
			}
			printf("\n");
		}
}

void main()
{
	int i,j,n,k,t,s;
	n=N;
	char path[N][N],q[N];
	GraphMatrix graph;
    initgraph(graph,n);
	dijkstra(graph,dist);
	for(i=0;i<N;i++){
		for(j=0;j<N;j++)
		    path[i][j]='#';
		q[i]='#';
	}
    for(i=0;i<N;i++)
		if(i!=0)path[i][N-1]=graph.vexs[0];
	for(j=1;j<N;j++){
		if(dist[j].prevex==0)
			path[j][N-2]=graph.vexs[j];
		k=j;
		if(dist[k].prevex!=0){
			
			 for(t=0;t<N-1;t++){
				 if(dist[k].prevex!=0&&dist[k].prevex!=-1){
				    k=dist[k].prevex;
                    path[j][N-2-t]=graph.vexs[k];
				 }//if

				 if(dist[k].prevex==0){ 
					  s=0;                                              
					  for(i=0;i<N-1;i++)
						  if(path[j][i]!='#'){
							  q[s]=path[j][i];  
							  s=s++;
					 }                                       
					 for(i=N-2;i>=0;i--){
						if(q[N-2-i]=='#')break;
							  path[j][i]=q[N-2-i];
					}
					path[j][i]=graph.vexs[j];               
				 }                                        

			   if(dist[k].prevex==0)break;   
			   
			 }   
		}
	}
	for(i=0;i<N;i++){
		if(path[i][N-2]=='#')
			printf("从起点%c没有到%c的路径\n",graph.vexs[0],graph.vexs[i]);
		if(path[i][N-2]=='#')continue;
         printf("从起点%c到%c的最短路径:",graph.vexs[0],graph.vexs[i]);
		for(j=6;j>=0;j--){
			if(path[i][j]=='#')break;
			 if(path[i][j-1]=='#')
			 printf("%c",path[i][j]);
			 else printf("%c---->",path[i][j]);
		} 
		printf("\t路径总长度:%d",dist[i].length);
			printf("\n"); 
	}
}