【数据结构】最短路径算法

最短路径：对于非网图来说，最短路径指两顶点之间经过的边数最少的路径。而对于网图来说，最短路径指的是两顶点之间经过的边上权值之和最少的路径。

这里介绍两种网图的最短路径算法：迪杰斯特拉算法（Dijkstra）和弗洛伊德算法（Floyd）。

Dijkstra算法：

算法并不是一下子就求出v0到v8的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求出更远顶点的最短路径，最终得到你要的结果。

代码：

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535

typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码，如OK等 */ 


typedef struct
{
	int vexs[MAXVEX];
	int arc[MAXVEX][MAXVEX];
	int numVertexes,numEdges;
}MGraph;

typedef int Patharc[MAXVEX];    /* 用于存储最短路径下标的数组 */
typedef int ShortPathTable[MAXVEX];/* 用于存储到各点最短路径的权值和 */

/* 构件图 */
void CreateMGraph(MGraph *G)
{
	int i,j;

	/* printf("请输入边数和顶点数:"); */
	G->numEdges=16;
	G->numVertexes=9;

	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
	{
		G->vexs[i]=i;
	}

	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
	{
		for ( j = 0; j < G->numVertexes; j++)
		{
			if (i==j)
				G->arc[i][j]=0;
			else
				G->arc[i][j] = G->arc[j][i] = INFINITY;
		}
	}

	G->arc[0][1]=1;
	G->arc[0][2]=5; 
	G->arc[1][2]=3; 
	G->arc[1][3]=7; 
	G->arc[1][4]=5; 

	G->arc[2][4]=1; 
	G->arc[2][5]=7; 
	G->arc[3][4]=2; 
	G->arc[3][6]=3; 
	G->arc[4][5]=3;

	G->arc[4][6]=6;
	G->arc[4][7]=9; 
	G->arc[5][7]=5; 
	G->arc[6][7]=2; 
	G->arc[6][8]=7;

	G->arc[7][8]=4;


	for(i = 0; i < G->numVertexes; i++)
	{
		for(j = i; j < G->numVertexes; j++)
		{
			G->arc[j][i] =G->arc[i][j];
		}
	}

}

/*  Dijkstra算法，求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] */    
/*  P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */  
void ShortestPath_Dijkstra(MGraph G,int v0,Patharc *P,ShortPathTable *D)
{    
	int v,w,k,min;    
	int final[MAXVEX];/* final[w]=1表示求得顶点v0至vw的最短路径 */
	for(v=0; v<G.numVertexes; v++)    /* 初始化数据 */
	{        
		final[v] = 0;			/* 全部顶点初始化为未知最短路径状态 */
		(*D)[v] = G.arc[v0][v];/* 将与v0点有连线的顶点加上权值 */
		(*P)[v] = -1;				/* 初始化路径数组P为-1  */       
	}

	(*D)[v0] = 0;  /* v0至v0路径为0 */  
	final[v0] = 1;    /* v0至v0不需要求路径 */        
	/* 开始主循环，每次求得v0到某个v顶点的最短路径 */   
	for(v=1; v<G.numVertexes; v++)   
	{
		min=INFINITY;    /* 当前所知离v0顶点的最近距离 */        
		for(w=0; w<G.numVertexes; w++) /* 寻找离v0最近的顶点 */    
		{            
			if(!final[w] && (*D)[w]<min)             
			{                   
				k=w;                    
				min = (*D)[w];    /* w顶点离v0顶点更近 */            
			}        
		}        
		final[k] = 1;    /* 将目前找到的最近的顶点置为1 */
		for(w=0; w<G.numVertexes; w++) /* 修正当前最短路径及距离 */
		{
			/* 如果经过v顶点的路径比现在这条路径的长度短的话 */
			if(!final[w] && (min+G.arc[k][w]<(*D)[w]))   
			{ /*  说明找到了更短的路径，修改D[w]和P[w] */
				(*D)[w] = min + G.arc[k][w];  /* 修改当前路径长度 */               
				(*P)[w]=k;        
			}       
		}   
	}
}

int main(void)
{   
	int i,j,v0;
	MGraph G;    
	Patharc P;    
	ShortPathTable D; /* 求某点到其余各点的最短路径 */   
	v0=0;
	
	CreateMGraph(&G);
	
	ShortestPath_Dijkstra(G,v0,&P,&D);  

	printf("最短路径倒序如下:n");    
	for(i=1;i<G.numVertexes;++i)   
	{       
		printf("v%d - v%d : ",i);
		j=i;
		while(P[j]!=-1)
		{
			printf("%d ",P[j]);
			j=P[j];
		}
		printf("n");
	}    
	printf("n源点到各顶点的最短路径长度为:n");  
	for(i=1;i<G.numVertexes;++i)        
		printf("v%d - v%d : %d n",G.vexs[0],G.vexs[i],D[i]);     
	return 0;
}

结果：

Floyd算法：

该算法完成了所有顶点到所有顶点的最短路径计算。

首先的准备两个矩阵D-1和P-1，D-1是网图的邻接矩阵，P-1初设为P[i][j]=j这样的矩阵，它主要用来存储路径。

得到D-1和P-1后，由表达式：D0[v][w]=min{D-1[v][w],D-1[v][0]+D-1[0][w]}得到D0和P0：

依次类推可以得到D1和P1，...D8和P8：

...

以v0到v8为例，P[0][8]=1，得到要经过顶点v1，然后将1取代0得到P[1][8]=2，说明要经过v2，然后将2取代1得到P[2][8]=4，说明要经过4，然后将4取代2得到P[4][8]=3，说明要经过v3，...，这样很容易推导出最终的最短路径值为v0->v1->v2->v4->v3->v6->v7->v8。

代码：

#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535

typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码，如OK等 */

typedef struct
{
	int vexs[MAXVEX];
	int arc[MAXVEX][MAXVEX];
	int numVertexes,numEdges;
}MGraph;

typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];

/* 构件图 */
void CreateMGraph(MGraph *G)
{
	int i,j;

	/* printf("请输入边数和顶点数:"); */
	G->numEdges=16;
	G->numVertexes=9;

	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
	{
		G->vexs[i]=i;
	}

	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
	{
		for ( j = 0; j < G->numVertexes; j++)
		{
			if (i==j)
				G->arc[i][j]=0;
			else
				G->arc[i][j] = G->arc[j][i] = INFINITY;
		}
	}

	G->arc[0][1]=1;
	G->arc[0][2]=5;
	G->arc[1][2]=3;
	G->arc[1][3]=7;
	G->arc[1][4]=5;

	G->arc[2][4]=1;
	G->arc[2][5]=7;
	G->arc[3][4]=2;
	G->arc[3][6]=3;
	G->arc[4][5]=3;

	G->arc[4][6]=6;
	G->arc[4][7]=9;
	G->arc[5][7]=5;
	G->arc[6][7]=2;
	G->arc[6][8]=7;

	G->arc[7][8]=4;


	for(i = 0; i < G->numVertexes; i++)
	{
		for(j = i; j < G->numVertexes; j++)
		{
			G->arc[j][i] =G->arc[i][j];
		}
	}

}

/* Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */
void ShortestPath_Floyd(MGraph G,ShortPathTable *D)
{
	int v,k;
	for(v=0; v<G.numVertexes; ++v) /* 初始化D与P */
	{
		for(w=0; w<G.numVertexes; ++w)
		{
			(*D)[v][w]=G.arc[v][w];	/* D[v][w]值即为对应点间的权值 */
			(*P)[v][w]=w;				/* 初始化P */
		}
	}
	for(k=0; k<G.numVertexes; ++k)
	{
		for(v=0; v<G.numVertexes; ++v)
		{
			for(w=0; w<G.numVertexes; ++w)
			{
				if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
				{/* 如果经过下标为k顶点路径比原两点间路径更短 */
					(*D)[v][w]=(*D)[v][k]+(*D)[k][w];/* 将当前两点间权值设为更小的一个 */
					(*P)[v][w]=(*P)[v][k];/* 路径设置为经过下标为k的顶点 */
				}
			}
		}
	}
}

int main(void)
{
	int v,k;
	MGraph G;

	Patharc P;
	ShortPathTable D; /* 求某点到其余各点的最短路径 */

	CreateMGraph(&G);

	ShortestPath_Floyd(G,&D);

	printf("各顶点间最短路径如下:n");
	for(v=0; v<G.numVertexes; ++v)
	{
		for(w=v+1; w<G.numVertexes; w++)
		{
			printf("v%d-v%d weight: %d ",v,D[v][w]);
			k=P[v][w];				/* 获得第一个路径顶点下标 */
			printf(" path: %d",v);	/* 打印源点 */
			while(k!=w)				/* 如果路径顶点下标不是终点 */
			{
				printf(" -> %d",k);	/* 打印路径顶点 */
				k=P[k][w];			/* 获得下一个路径顶点下标 */
			}
			printf(" -> %dn",w);	/* 打印终点 */
		}
		printf("n");
	}

	printf("最短路径Dn");
	for(v=0; v<G.numVertexes; ++v)
	{
		for(w=0; w<G.numVertexes; ++w)
		{
			printf("%dt",D[v][w]);
		}
		printf("n");
	}
	printf("最短路径Pn");
	for(v=0; v<G.numVertexes; ++v)
	{
		for(w=0; w<G.numVertexes; ++w)
		{
			printf("%d ",P[v][w]);
		}
		printf("n");
	}

	return 0;
}

结果：

比较：

1，算法时间复杂度都是O（n^3）；

2，如果需要求所有顶点到所有顶点的最短路径时，Floyd算法是不错的选择；

3，在这里求最短路径的两个算法举例都是无向图，但它们对有向图依然有效，因为二者的差异仅仅是邻接矩阵是否对称而已。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!