⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 shortestway.cpp

📁 数据结构最短路径算法实现
💻 CPP
字号:
🔍 
/*
林凌
2005131346
05级计算机1班

实验内容:
1.创建图。采用邻接表或邻接矩阵均可，自己编写或采用教案中的范例。
2.输入出发顶点。
3．定义子函数，求从输入顶点到其它各顶点的最短路径

实验要求:
1.采用结构化程序设计。函数的名，返回类型，参数传递均自己定义。
2.用主函数调用子函数，完成图创建、出发点输入，求最短路径。
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INFINITY 999999   //定义无穷大
#define MAX_VERTEX_NUM 100   //定义数组大小

typedef struct ArcCell
{
 int adj;
 int *info;
}AreCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  //顶点的数据结构,但是本程序中没有使用*info.

typedef struct
{
 int       vexs[MAX_VERTEX_NUM];//顶点数组
 AdjMatrix arcs;                //弧
 int       vexnum,arcnum;       //顶点数,弧段数
 int       kind;                //图或网的类型
}MGraph;//图(网)的数据结构

//定义程序中使用到的函数
int CreateDG(MGraph &G);
int CreateDN(MGraph &G);
int CreateUDG(MGraph &G);
int CreateUDN(MGraph &G);
void Shortestway_N(MGraph G);
void Shortestway_G(MGraph G);
void printPath(int P[MAX_VERTEX_NUM], int i);
void outprint(MGraph &G, int vx, int P[MAX_VERTEX_NUM],int D[MAX_VERTEX_NUM]);


int LocateVex(int v,MGraph G) //确定点在G中的位置的函数
{
 int index;
 for(int i=0;i<G.vexnum;++i)
 {
  if(G.vexs[i]==v)
  {
   index=i;
   break;
  }
 }
 return index;
}

void CreateGraph(MGraph &G)//创建图或网的函数.包含了图或网的最短路径
{
	printf("请选择：1=DG=有向图，2=DN=有向网，3=UDG=无向图，4=UDN=无向网，以回车结束。\n");
	scanf("%d",&G.kind);
	switch(G.kind)       //选择创建什么图
	{
	case 1:CreateDG(G);
		break;
	case 2:CreateDN(G);
		break;
	case 3:CreateUDG(G);
		break;
	case 4:CreateUDN(G);
		break;
	default:printf("出错咯~只能选择1-4,^.^\n\n");
		    CreateGraph(G);
		break;
	}
}

int CreateDG(MGraph &G)//创建有向图
{ 
 int v1,v2;
 printf("%s\n","输入顶点数和弧数:");
 scanf("%d%d",&G.vexnum,&G.arcnum);
 printf("%s%d%s\n","输入",G.vexnum,"个顶点,以回车隔开(即为顶点命名,命名必须从0开始,例如2个顶点则输入0回车1回车):");
 for(int i=0;i<G.vexnum;++i)
	 scanf("%d",&G.vexs[i]); //构造顶点向量
 for(i=0;i<G.vexnum;++i)     //初始化临接矩阵
  for(int j=0;j<G.vexnum;++j)
  {
   G.arcs[i][j].adj=0;
   G.arcs[i][j].info=NULL;
  }
 printf("%s%d%s\n","输入",G.arcnum,"条弧的起始点,终点,以回车间隔:");
 for(i=0;i<G.arcnum;++i) //构造邻接矩阵
 {
  int m,n;
  scanf("%d%d",&v1,&v2);
  m=LocateVex(v1,G);     
  n=LocateVex(v2,G);     //确定V1和V2在G中的位置
  G.arcs[m][n].adj=1;
 }
 for(i=0;i<G.vexnum;++i)   //打印矩阵
 {
  for(int j=0;j<G.vexnum;++j)
  {
   if(G.arcs[i][j].adj == 0)
    printf("0\t");
   else
    printf("%d\t", G.arcs[i][j].adj);
  }
  printf("\n");
 }

 Shortestway_G(G);  //求最短路径

 return 1;
}


int CreateDN(MGraph &G)  //构造有向网
{ 
 int v1,v2,w;
 printf("%s\n","输入顶点数和弧数:");
 scanf("%d%d",&G.vexnum,&G.arcnum);
 printf("%s%d%s\n","输入",G.vexnum,"个顶点,以回车隔开(即为顶点命名,命名必须从0开始,例如2个顶点则输入0回车1回车):");
 for(int i=0;i<G.vexnum;++i)
	 scanf("%d",&G.vexs[i]);
 for(i=0;i<G.vexnum;++i) 
  for(int j=0;j<G.vexnum;++j)
  {
   G.arcs[i][j].adj=INFINITY;
   G.arcs[i][j].info=NULL;
  }
 printf("%s%d%s\n","输入",G.arcnum,"条弧的起始点,终点,权值,以回车间隔:");
 for(i=0;i<G.arcnum;++i) 
 {
  int m,n;
  scanf("%d%d%d",&v1,&v2,&w);
  m=LocateVex(v1,G);
  n=LocateVex(v2,G);
  G.arcs[m][n].adj=w;
 }
 for(i=0;i<G.vexnum;++i) 
 {
  for(int j=0;j<G.vexnum;++j)
  {
   if(G.arcs[i][j].adj == INFINITY)
    printf("∞\t");
   else
    printf("%d\t", G.arcs[i][j].adj);
  }
  printf("\n");
 }
 
 Shortestway_N(G);

 return 1;
}

int CreateUDG(MGraph &G) //构造无向图
{ 
 int v1,v2;
 printf("%s\n","输入顶点数和弧数:");
 scanf("%d%d",&G.vexnum,&G.arcnum);
 printf("%s%d%s\n","输入",G.vexnum,"个顶点,以回车隔开(即为顶点命名,命名必须从0开始,例如2个顶点则输入0回车1回车):");
 for(int i=0;i<G.vexnum;++i) 
	 scanf("%d",&G.vexs[i]);
 for(i=0;i<G.vexnum;++i) 
  for(int j=0;j<G.vexnum;++j)
  {
   G.arcs[i][j].adj=0;
   G.arcs[i][j].info=NULL;
  }
 printf("%s%d%s\n","输入",G.arcnum,"条弧的起始点,终点,以回车间隔:");
 for(i=0;i<G.arcnum;++i) 
 {
  int m,n;
  scanf("%d%d",&v1,&v2);
  m=LocateVex(v1,G);
  n=LocateVex(v2,G);
  G.arcs[m][n].adj=1;
  G.arcs[n][m].adj=1; //置<v1,v2>的对称弧<v2,v1>
 }
 for(i=0;i<G.vexnum;++i) 
 {
  for(int j=0;j<G.vexnum;++j)
  {
   if(G.arcs[i][j].adj == 0)
    printf("0\t");
   else
    printf("%d\t", G.arcs[i][j].adj);
  }
  printf("\n");
 }

 Shortestway_G(G);

 return 1;
}


int CreateUDN(MGraph &G)  //构造无向网 
{ 
 int v1,v2,w;
 printf("%s\n","输入顶点数和弧数:");
 scanf("%d%d",&G.vexnum,&G.arcnum);
 printf("%s%d%s\n","输入",G.vexnum,"个顶点,以回车隔开(即为顶点命名,命名必须从0开始,例如2个顶点则输入0回车1回车):");
 for(int i=0;i<G.vexnum;++i)
	 scanf("%d",&G.vexs[i]);
 for(i=0;i<G.vexnum;++i) 
  for(int j=0;j<G.vexnum;++j)
  {
   G.arcs[i][j].adj=INFINITY;
   G.arcs[i][j].info=NULL;
  }
 printf("%s%d%s\n","输入",G.arcnum,"条弧的起始点,终点,权值,以回车间隔:");
 for(i=0;i<G.arcnum;++i) 
 {
  int m,n;
  scanf("%d%d%d",&v1,&v2,&w);
  m=LocateVex(v1,G);
  n=LocateVex(v2,G);
  G.arcs[m][n].adj=w;
  G.arcs[n][m].adj=w;   //置<v1,v2>的对称弧<v2,v1>
 }
 for(i=0;i<G.vexnum;++i) 
 {
  for(int j=0;j<G.vexnum;++j)
  {
   if(G.arcs[i][j].adj == INFINITY)
    printf("∞\t");
   else
    printf("%d\t", G.arcs[i][j].adj);
  }
  printf("\n");
 }
 
 Shortestway_N(G);

 return 1;
}

#define TRUE 1
#define FALSE 0

void Shortestway_N(MGraph G)//求网的最短路径
{
     int P[MAX_VERTEX_NUM],D[MAX_VERTEX_NUM],final[MAX_VERTEX_NUM]; //定义P向量保存到达端点的前一个点，
	                                                                //D保存路径长度，final标志是否求得最短路径
	 int v,w,i,m,vx,min;
	 printf("请输入起点:\n");
	 scanf("%d",&vx);
	 m=LocateVex(vx,G);       //得到起始点
     for(v=0;v<G.vexnum;v++)   //得到D和P的初始值
	 {
		  final[v]=0;
		  D[v]=G.arcs[m][v].adj;
		  if(D[v]<INFINITY)
		  {
			  P[v]=m;         
		  }
		  else
		  {
			  P[v]=-1;
		  }
	 }

	 D[m]=0;
	 final[m]=1;   //起始点自身‘初始化’

     //开始求最短路径的主循环
	 for(i=0;i<G.vexnum-1;i++)  
	 {
		 min=INFINITY;
		 for(w=0;w<G.vexnum;w++) //求得当前所有路径中长度最小的路径及其长度
		 {
			 if(!final[w])
				 if(D[w]<min)
				 {
					 v=w;
					 min=D[w];
				 }
				 else          //如果起始点到各顶点都没有最短路径的情况
				 {
					 v=m;
				 }
		 }
		 final[v]=1;         //设置该点的最短路径为以求得
		 for(w=0;w<G.vexnum;w++)   //更新当前最短路径及该路径终点前的点。即P
		 {
			 if(!final[w]&&(min+G.arcs[v][w].adj<D[w]))
			 {
				 D[w]=min+G.arcs[v][w].adj;
				 P[w]=v;
			 }
		 }
	 }
     outprint(G,vx,P,D);  //打印最短路径表
}

void Shortestway_G(MGraph G)  //求图的最短路径
{
     int P[MAX_VERTEX_NUM],D[MAX_VERTEX_NUM],final[MAX_VERTEX_NUM];
	 int v,i,m,vx,a,b;
	 printf("请输入起点:\n");
	 scanf("%d",&vx);
	 m=LocateVex(vx,G);
     for(v=0;v<G.vexnum;v++)  //得到D和P的初始值
	 {
		  final[v]=0;
		  D[v]=G.arcs[m][v].adj;
		  if(D[v]==1)           
		  {
			  P[v]=m;
			  final[v]=1;  //如果有D[w]==1则求得起始点到w的最短路径。
		  }
		  else
		  {
			  P[v]=-1;
		  }
	 }

	 D[m]=0;
	 final[m]=1;

     for(b=0;b<G.vexnum;b++)
	 {
		 if(final[b])
		 {
	 for(a=0;a<G.vexnum;a++)  //更新当前最短路径及该路径终点前的点。即P
		 {
			 if(!final[a]&&(G.arcs[b][a].adj>0))  
			 {
				 if(D[a]!=0&&D[a]+G.arcs[b][a].adj<D[a])  //找到更短的路径则替换原来路径
				 {
				 D[a]=D[b]+G.arcs[b][a].adj;
				 P[a]=b;
				 }
				 else
				 {
				 if(D[a]==0)      
				 {
                  D[a]=D[b]+G.arcs[b][a].adj;
				  P[a]=b;
				 }
				 }
			 }
		 }
		 }
	 }
	 for(i=0;i<G.vexnum;i++)
	 {
		 printf("P[%d]=%d\t",i,P[i]);
	 }
     outprint(G,vx,P,D);
}

void outprint(MGraph &G, int vx, int P[MAX_VERTEX_NUM], int D[MAX_VERTEX_NUM]) //打印最短路径表
{
 int i;
 printf("\n");
 printf("===============================================================");
 printf("\n");
 printf("\n起始点\t终点\t最短路径长度\t最短路径\n\n");
 for(i=0; i<G.vexnum; i++)
 {
   printf("v%d\t",vx);
   printf("v%d\t",i);
   if(D[i]==INFINITY)
   {
	  printf("∞\t\t");
   }
   else
   {
   printf("%-4d\t\t", D[i]);
   }
   if(D[i]==INFINITY)  //如果D[i]为无穷大，则没有最短路径
   {
	   printf("none");
   }
   else
   {
   printPath(P,i);
   }
   printf("\n");
  }
 printf("\n");
 printf("===============================================================");
 printf("\n");
}

void printPath(int P[MAX_VERTEX_NUM], int i)  //打印最短路径
{
  if (P[i] == -1)
  {
  printf("v%d -> ", i);
  return;
  }
  else
  {
  printPath(P, P[i]);  //递归调用自身
  printf("v%d -> ", i);
 }
}

void main()  //主函数
{
 MGraph G;
 CreateGraph(G);
}

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -