数据结构 求最短路径有关问题

数据结构 求最短路径问题

问题描述： 求任意两个城市之间的最短路径
基本要求：
（1）能够判断任意两个城市之间是否有通路
（2）如果有通路，找到这条最短路经

PS:任意两个城市之间的图粘贴不了，所以就上传了。

这是数据结构的课程设计，求编程代码，最好带有点注释的……
希望各大神帮帮忙！！谢谢！！
------解决方案--------------------

#include<stdio.h>

#include<stdlib.h>

#define MAXINT 5000

#define VEX_NUM 7

#define ARC_NUM 10

typedef struct{

	char vexs[VEX_NUM];

	int arcs[VEX_NUM][VEX_NUM];

	}Mgraph;

void creat_Mgraph(Mgraph *G);

void Dijkstra(Mgraph Gn,int v,int path[],int dist[]);

void Putpath(int v,int p[],int d[]);

void printpath(int v,int u,int p[],int d[]);

main()

{

        char city[7][20]={"beijing","xian","zhengzhou","xuzhou","chengdu","guangzhou","shanghai"｝；

	Mgraph Gn;

	int i,m,n;

	int path[VEX_NUM],dist[VEX_NUM];

	char s[4];

	for(;;)

	{

		printf("1.建立交通图的存储结构\n");

		printf("2.求某城市到所有城市的最短路径\n");

		printf("3.求任意两个城市之间的最短路径\n");

		printf("4.退出\n");

        gets(s);

		switch(*s)

		{

		  case'1':creat_Mgraph(&Gn);

			  break;

		  case'2':printf("请输入城市:\n");

			  scanf("%d",&i);

			  Dijkstra(Gn,i,path,dist);

			  Putpath(i,path,dist);

			  break;

		  case'3':printf("请输入城市：\n");

			  scanf("%d,%d",&m,&n);

			  Dijkstra(Gn,m,path,dist);

			  printpath(m,n,path,dist);

			  break;

		  case'4':exit(0);

			  break;

		}

	}

}

void creat_Mgraph(Mgraph *G)

{

		int i,j,k,w;

		printf("\n inuput vextex:");

		for(i=0;i<VEX_NUM;i++)

		     scanf("%c",&G->vexs[i]);

		for(i=0;i<VEX_NUM;i++)

		for(j=0;j<VEX_NUM;j++)

		     G->arcs[i][j]=MAXINT;

		printf("\n input edge(i,j,w):\n");

		for(k=1;k<=ARC_NUM;k++)

		{

		    scanf("%d,%d,%d",&i,&j,&w);

		    G->arcs[i][j]=w;

		    G->arcs[j][i]=w;

		}

}

void Putpath(int v,int p[],int d[])

{

		int i,j,next;

		for(i=0;i<VEX_NUM;i++)

		  if(d[i]<MAXINT&&i!=v)

		  {

			printf("%c<--",city[i]);

			next=p[i];

			while(next!=v)

			{

			    printf("%c<--",city[next]);

			    next=p[next];

			}

		    printf("%c:%d\n",city[v],d[i]);

		  }

}

void printpath(int v,int u,int p[],int d[])

{

     int i,j,next;

     for(i=0;i<VEX_NUM;i++)

	if(d[i]<MAXINT&&i==u)

        {  

            printf("%c<--",city[i]);

            next=p[i];

            while(next!=v)

            {  

                 printf("%c<--",city[next]);