用户注册



邮箱：

密码：

用户登录


邮箱：

密码：
记住登录一个月忘记密码？

发表随想


还能输入：200字
云代码 - c++代码库

最短路径算法

2012-09-23 作者： 神马举报

[c++]代码库

#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INFINITY 30000    //定义一个权值的最大值
#define MAX_VERTEX_NUM 20 //图的最大顶点数
enum BOOL {False,True};
typedef struct
{
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
	int vexnum,arcnum;                //图的当前顶点和边数
} Graph;
void CreateGraph ( Graph & ); //生成图的邻接矩阵
void ShortestPath_DiJ ( Graph,int,int[][MAX_VERTEX_NUM],int[] );
//用迪杰斯特拉算法求从某一源点到其余顶点的最短路径
void Print_ShortestPath ( Graph,int,int[][MAX_VERTEX_NUM],int[] );
//显示最短路径
void main()
{
	Graph G;  //采用邻接矩阵结构的图
	char j='y';
	int u;
	int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //存放从源点到各顶点的最短路径
	int D[MAX_VERTEX_NUM];                 //存放从源点到各顶点的最短路径的距离
	textbackground ( 3 );  //设定屏幕颜色
	textcolor ( 15 );
	clrscr();
//------------------程序解说----------------------------
	printf ( "本程序将演示利用迪杰斯特拉算法求\n从图的一点到其余顶点的最短路径.\n" );
	printf ( "首先输入图的顶点数和弧数.\n格式：顶点数，弧数；例如:5,7\n" );
	printf ( "然后输入各弧和权值.\n格式：弧尾，弧头，权值；例如:\n1,2,10\n1,3,18\n2,4,5\n3,2,5\n4,3,2\n4,5,2\n5,3,2\n" );
	printf ( "再输入从哪个顶点出发，例如:1\n" );
	printf ( "程序将会找出从1到其余顶点的最短路径.\n" );
	printf ( "10  1->2\n17  1->2->4->3\n15  1->2->4\n17  1->2->4->5\n" );
//------------------------------------------------------
	while ( j!='N'&&j!='n' )
	{
		CreateGraph ( G );    //生成邻接矩阵结构的图
		printf ( "从哪个顶点出发:" );
		scanf ( "%d",&u );  //输入迪杰斯特拉算法中的起始顶点
		ShortestPath_DiJ ( G,u,P,D ); //利用迪杰斯特拉算法求最短路径
		Print_ShortestPath ( G,u,P,D ); //显示最短路径
		printf ( "最短路径演示完毕，继续进行吗?(Y/N)" );
		scanf ( " %c",&j );
	}
}

void CreateGraph ( Graph &G )
{//构造邻接矩阵结构的图G
	int i,j;
	int start,end,weight;
	printf ( "请输入图的顶点数和弧数(顶点数，弧数):" );
	scanf ( "%d,%d",&G.vexnum,&G.arcnum ); //输入图的顶点数和边数
	for ( i=1; i<=G.vexnum; i++ )
		for ( j=1; j<=G.vexnum; j++ )
			G.arcs[i][j]=INFINITY; //初始化邻接矩阵
	printf ( "输入各弧和权值，格式：弧尾，弧头，权值\n" );
	for ( i=1; i<=G.arcnum; i++ )
	{
		scanf ( "%d,%d,%d",&start,&end,&weight ); //输入边的起点和终点及权值
		G.arcs[start][end]=weight;
	}
}
void ShortestPath_DiJ ( Graph G,int v0,int P[][MAX_VERTEX_NUM],int D[] )
{//用迪杰斯特拉算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权路径长度D[v]
//若P[v][0]≠0,表明从源点出发存在一条到顶点v的最短路径，该路径存放在P[v]中
//final[v]为True则表明已经找到从v0到v的最短路径
	int i,j,w,v;
	int min;
	BOOL final[MAX_VERTEX_NUM];
	for ( v=1; v<=G.vexnum; v++ )   //初始化
	{
		final[v]=False;
		D[v]=G.arcs[v0][v];
		for ( i=0; i<=G.vexnum; i++ ) P[v][i]=0; //设空路径
		//if(D[v]<INFINITY) P[v][0]=v0; //若从v0到v有直达路径
	}
	D[v0]=0;
	final[v0]=True; //初始时，v0属于S集
//开始主循环，每次求得v0到某个顶点v的最短路径，并加v到S集
	for ( i=1; i<=G.vexnum; i++ )  //寻找其余G.vexnum-1个顶点
	{
		v=0;
		min=INFINITY;
		for ( w=1; w<=G.vexnum; w++ )   //寻找当前离v0最近的顶点v
			if ( ( !final[w] ) && ( D[w]<min ) )
				{v=w; min=D[w];}
		if ( !v ) break;  //若v=0表明所有与v0有通路的顶点均已找到了最短路径，退出主循环
		final[v]=True; //将v加入S集
		for ( j=0; P[v][j]!=0; j++ ) ;
		P[v][j]=v;     //将路径P[v]延伸到顶点v
		for ( w=1; w<=G.vexnum; w++ ) //更新当前最短路径及距离
			if ( !final[w]&& ( min+G.arcs[v][w]<D[w] ) )
			{
				D[w]=min+G.arcs[v][w];
				for ( j=0; P[v][j]!=0; j++ ) P[w][j]=P[v][j];
			}
	}
}

void Print_ShortestPath ( Graph G,int v0,int P[][MAX_VERTEX_NUM],int D[] )
{//显示从顶点u到其余顶点的最短路径及距离
	int v,j;
	printf ( "The shortest path from Vertex %d to the other Vertex:\n" );
	for ( v=1; v<=G.vexnum; v++ )
	{
		if ( P[v][0]==0 ) continue; //表明顶点v0到顶点v没有通路
		printf ( "%-4d",D[v] );
		printf ( "%d->",v0 );
		for ( j=0; P[v][j]!=0; j++ )
			printf ( "%d->",P[v][j] );
		printf ( "\b\b  \n" );
	}
}

typedef struct
{
	int arcs[MAX_NUM][MAX_NUM]; //邻接矩阵
	int vexnum,arcnum;                //图的当前顶点和边数
} Graph;
void CreateGraph ( Graph & ); //生成图的邻接矩阵
void ShortestPath_Floyd ( Graph,BOOL[][MAX_NUM][MAX_NUM],int[][MAX_NUM] );
//用弗洛依德算法求每对顶点之间的最短路径
void Print_ShortestPath ( Graph,BOOL[][MAX_NUM][MAX_NUM],int[][MAX_NUM] );
//显示用弗洛依德算法所求得的最短路径
void Print_OnePath ( int,int,int,BOOL[][MAX_NUM][MAX_NUM] );
//显示一对顶点之间的最短路径
void main()
{
	Graph G;  //采用邻接矩阵结构的图
	char j='y';
	int u;
	BOOL P[MAX_NUM][MAX_NUM][MAX_NUM]; //存放每对顶点的最短路径
	int D[MAX_NUM][MAX_NUM];                 //存放每对顶点的最短路径的距离
	textbackground ( 3 );  //设定屏幕颜色
	textcolor ( 15 );
	clrscr();
//------------------程序解说----------------------------
	printf ( "本程序将演示利用弗洛依德算法求图的每一对顶点之间的最短路径。\n" );
	printf ( "首先输入图的顶点和弧的数目。\n例如：3,5\n" );
	printf ( "接着输入弧(i,j)和其权值。\n例如：\n1,2,4\n2,1,6\n1,3,11\n3,1,3\n2,3,2\n" );
	printf ( "程序将会显示出每对顶点之间的最短路径值和所经过的路径：\n" );
	printf ( "4  1->2\n6  1->2->3\n5  2->3->1\n2  2->3\n3  3->1\n7  3->1->2\n" );
//------------------------------------------------------
	while ( j!='N'&&j!='n' )
	{
		CreateGraph ( G );    //生成邻接矩阵结构的图
		ShortestPath_Floyd ( G,P,D ); //利用弗洛依德算法求最短路径
		Print_ShortestPath ( G,P,D ); //显示每对顶点之间的最短路径
		printf ( "继续执行吗?(Y/N)" );
		scanf ( " %c",&j );
	}
	printf ( "程序运行结束，按任意键退出窗口!" );
	getch();
}

void CreateGraph ( Graph &G )
{//构造邻接矩阵结构的图G
	int i,j;
	int start,end,weight;
	printf ( "请输入顶点和弧的数目，格式：顶点数，弧数\n" );
	scanf ( "%d,%d",&G.vexnum,&G.arcnum ); //输入图的顶点数和边数
	for ( i=1; i<=G.vexnum; i++ )
		for ( j=1; j<=G.vexnum; j++ )
			G.arcs[i][j]=INFINITY; //初始化邻接矩阵
	printf ( "请输入各条弧和其权值，格式：弧尾，弧头，权值：\n" );
	for ( i=1; i<=G.arcnum; i++ )
	{
		scanf ( "%d,%d,%d",&start,&end,&weight ); //输入边的起点和终点及权值
		G.arcs[start][end]=weight;
	}
}
void ShortestPath_Floyd ( Graph G,BOOL P[][MAX_NUM][MAX_NUM],int D[][MAX_NUM] )
{//用弗洛依德算法求有向网G的每对顶点v和w之间的最短路径P[v][w]
//及其带权路径长度D[v][w],
//若P[v][w][u]为True,表明u是从v到w当前求得最短路径上的顶点
	int u,v,w,i;
	for ( v=1; v<=G.vexnum; v++ ) //各对顶点之间的初始已知路径及距离
		for ( w=1; w<=G.vexnum; w++ )
		{
			D[v][w]=G.arcs[v][w];
			for ( u=1; u<=G.vexnum; u++ ) P[v][w][u]=False;
			if ( D[v][w]<INFINITY )  //从v到w有直接路径
				{P[v][w][v]=True; P[v][w][w]=True;}
		}
	for ( u=1; u<=G.vexnum; u++ )
		for ( v=1; v<=G.vexnum; v++ )
			for ( w=1; w<=G.vexnum; w++ )
				if ( D[v][u]+D[u][w]<D[v][w]&&v!=w ) //从v经u到w的一条路径更短
				{
					D[v][w]=D[v][u]+D[u][w];
					for ( i=1; i<=G.vexnum; i++ )
						if ( P[v][u][i]||P[u][w][i] ) P[v][w][i]=True;
				}
}

void Print_ShortestPath ( Graph G,BOOL P[][MAX_NUM][MAX_NUM],int D[][MAX_NUM] )
{//显示每对顶点之间的最短路径及距离
	int v,w,j;
	printf ( "最短路径：\n" );
	for ( v=1; v<=G.vexnum; v++ )
		for ( w=1; w<=G.vexnum; w++ )
			if ( D[v][w]<INFINITY )  //顶点v和w之间有通路
			{
				printf ( "%-5d",D[v][w] ); //从v到w的最短距离
				Print_OnePath ( v,w,G.vexnum,P ); //显示从v到w的最短路径
				printf ( "\n" );
			}
}
void Print_OnePath ( int v,int w,int num,BOOL P[][MAX_NUM][MAX_NUM] )
{//显示从v到w的最短路径
	int i;
	for ( i=1; i<=num; i++ )
		if ( i!=v&&i!=w&&P[v][w][i]==True ) break;
	if ( i>num ) printf ( "%d->%d",v,w ); //说明从v到w不需经过其它的顶点
	else
	{
		Print_OnePath ( v,i,num,P ); //否则从v到w需经过顶点i，先显示从v到i的最短路径
		if ( i<10 ) printf ( "\b" );  //控制显示格式，消除多余的"->"
		else printf ( "\b\b" );
		Print_OnePath ( i,w,num,P ); //显示从i到w的最短路径
	}
}


网友评论    (发表评论)

共2 条评论 1/1页

发表评论：

评论须知：

  • 1、评论每次加2分，每天上限为30；
  • 2、请文明用语，共同创建干净的技术交流环境；
  • 3、若被发现提交非法信息，评论将会被删除，并且给予扣分处理，严重者给予封号处理；
  • 4、请勿发布广告信息或其他无关评论，否则将会删除评论并扣分，严重者给予封号处理。


扫码下载

加载中，请稍后...

输入口令后可复制整站源码

加载中，请稍后...