C++编程练习(11)----“图的最短路径问题“（Dijkstra算法、Floyd算法）

1、Dijkstra算法

求一个顶点到其它所有顶点的最短路径，是一种按路径长度递增的次序产生最短路径的算法。

算法思想：

按路径长度递增次序产生算法：

把顶点集合V分成两组：

（1）S：已求出的顶点的集合（初始时只含有源点V0）

（2）V-S=T：尚未确定的顶点集合

将T中顶点按递增的次序加入到S中，保证：

（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度

（2）每个顶点对应一个距离值

S中顶点：从V0到此顶点的长度

T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度

依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和

（反证法可证）

求最短路径步骤

算法步骤如下：

1. 初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值

若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值

若不存在<V0,Vi>，d(V0,Vi)为∞

2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S

3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值

重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

2、Floyd算法

求所有顶点到所有顶点的最短路径。

算法思想：

1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。

把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=无穷大。定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值变小，则D[i,j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。

比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。

优缺点：

Floyd算法适用于APSP(All Pairs Shortest Paths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。

优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单

缺点：时间复杂度比较高，不适合计算大量数据。

算法具体代码如下：

/* Graph.h头文件 */
/*包含图的建立：图的深度优先遍历、图的广度优先遍历*/
/*包含图的最小生成树：Prim 算法、Kruskal 算法*/
/*包含图的最短路径算法：Dijkstra算法、Floyd算法*/
#include<iostream>
#include"LinkQueue.h"
#define MAXVEX 100
#define MAXEDGE 100
#define INFINITY 65535
#define TRUE 1
#define FALSE 0
typedef char VertexType;
typedef int EdgeType;
typedef int Boolean;
typedef int Patharc[MAXVEX];		/*用于存储最短路径下标的数组*/
typedef int ShortPathTable[MAXVEX];		/*用于存储到各点最短路径的权值和*/
typedef int Pathmatrix[MAXVEX][MAXVEX];
typedef int ShortPathTable_Floyd[MAXVEX][MAXVEX];

using namespace std;

/*邻接矩阵方式建立图*/
class MGraph{
public:
	VertexType vexs[MAXVEX];
	EdgeType arc[MAXVEX][MAXVEX];
	int numVertexes,numEdges;
};

/*建立无向网图的邻接矩阵表示*/
void CreateMGraph(MGraph *G)
{
	int i,j,k,w;
	cout<<"输入顶点数和边数："<<endl;
	cin>>G->numVertexes>>G->numEdges;
	cin.clear();
	cout<<"输入顶点信息："<<endl;
	for(i=0;i<G->numVertexes;i++)
	{
		cin>>G->vexs[i];
		cin.clear();
	}
	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]=INFINITY;
		}
	for(k=0;k<G->numEdges;k++)
	{
		cout<<"输入边（vi,vj）上的下标i，下标j和权w:"<<endl;
		cin>>i>>j>>w;
		cin.clear();
		G->arc[i][j]=w;
		G->arc[j][i]=G->arc[i][j];
	}
}

/*邻接矩阵的深度优先递归算法*/
Boolean visited[MAXVEX];	/*访问标志的数组*/
void DFS(MGraph G,int i)
{
	int j;
	visited[i]=TRUE;
	cout<<G.vexs[i];	/*打印顶点，也可以其他操作*/
	for(j=0;j<G.numVertexes;j++)
		if(G.arc[i][j]==1 && !visited[j])
			DFS(G,j);	/*对为访问的邻接顶点递归调用*/
}
/*邻接矩阵的深度优先遍历操作*/
void DFSTraverse(MGraph G)
{
	cout<<"\n深度优先遍历结果为："<<endl;
	int i;
	for(i=0;i<G.numVertexes;i++)
		visited[i]=FALSE;	/*初始化所有顶点状态都是未访问过状态*/
	for(i=0;i<G.numVertexes;i++)
		if(!visited[i])	/*对未访问过的顶点调用DFS，若是连通图，只会执行一次*/
			DFS(G,i);
	cout<<endl;
}

/*邻接矩阵的广度遍历算法*/
void BFSTraverse(MGraph G)
{
	cout<<"广度优先遍历结果为："<<endl;
	int i,j;
	LinkQueue Q;
	for(i=0;i<G.numVertexes;i++)
		visited[i]=FALSE;
	for(i=0;i<G.numVertexes;i++)
	{
		if(!visited[i])
		{
			visited[i]=TRUE;
			cout<<G.vexs[i];
			Q.EnQueue(i);
			while(!Q.QueueEmpty())
			{
				Q.DeQueue(&i);
				for(j=0;j<G.numVertexes;j++)
				{
					if(G.arc[i][j]==1 && !visited[j])
					{
						visited[j]=TRUE;
						cout<<G.vexs[j];
						Q.EnQueue(j);
					}
				}
			}
		}
	}
	cout<<endl;
}

/* Prim算法生成最小生成树 */
void MiniSpanTree_Prim(MGraph G)
{
	cout<<"Prim算法生成最小生成树，结果为："<<endl;
	int min,i,j,k;
	int adjvex[MAXVEX];
	int lowcost[MAXVEX];
	lowcost[0]=0;
	adjvex[0]=0;
	for(i=1;i<G.numVertexes;i++)
	{
		lowcost[i]=G.arc[0][i];
		adjvex[i]=0;
	}
	for(i=1;i<G.numVertexes;i++)
	{
		min=INFINITY;
		j=1;k=0;
		while(j<G.numVertexes)
		{
			if(lowcost[j]!=0 && lowcost[j]<min)
			{
				min=lowcost[j];
				k=j;
			}
			j++;
		}
		cout<<"("<<adjvex[k]<<","<<k<<")"<<endl;
		lowcost[k]=0;
		for(j=1;j<G.numVertexes;j++)
		{
			if(lowcost[j]!=0 && G.arc[k][j]<lowcost[j])
			{
				lowcost[j]=G.arc[k][j];
				adjvex[j]=k;
			}
		}
	}
	cout<<endl;
}

/* Kruskal 算法生成最小生成树 */

class Edge{		/*对边集数组Edge结构的定义*/
public:
	int begin;
	int end;
	int weight;
};

void Swap(Edge *edges,int i,int j)		/* 交换权值 以及头和尾 */
{
	int temp;
	temp=edges[i].begin;
	edges[i].begin=edges[j].begin;
	edges[j].begin=temp;
	temp=edges[i].end;
	edges[i].end=edges[j].end;
	edges[j].end=temp;
	temp=edges[i].weight;
	edges[i].weight=edges[j].weight;
	edges[j].weight=temp;
}

void sort(Edge edges[],MGraph *G)		/* 对权值进行排序 */
{
	int i,j;
	for ( i=0;i<G->numEdges;i++)
	{
		for ( j=i+1;j<G->numEdges;j++)
		{
			if (edges[i].weight>edges[j].weight)
			{
				Swap(edges,i,j);
			}
		}
	}
	cout<<"权排序之后的为:"<<endl;
	for (i=0;i<G->numEdges;i++)
	{
		cout<<"("<<edges[i].begin<<","<<edges[i].end<<")"<<endl;
	}
}

int Find(int *parent,int f)		/*查找连线顶点的尾部下标*/
{
	while (parent[f]>0)
		f=parent[f];
	return f;
}

void MiniSpanTree_Kruskal(MGraph G)
{
	int i,j,n,m;
	Edge edges[MAXEDGE];
	int parent[MAXVEX];

	/*将邻接数组G转化为边集数组edges并按权由小到大排序*******BEGIN*********/
	int k=0;
	for ( i=0;i<G.numVertexes-1;i++)
	{
		for (j=i+1;j<G.numVertexes;j++)
		{
			if (G.arc[i][j]<INFINITY)
			{
				edges[k].begin=i;
				edges[k].end =j;
				edges[k].weight=G.arc[i][j];
				k++;
			}
		}
	}
	sort(edges, &G);
	/***************END***********************/

	for (i=0;i<G.numVertexes;i++)
		parent[i]=0;	/* 初始化数组值为0 */
	cout<<"Kruskal 算法生成最小生成树，结果为："<<endl;
	for (i=0;i<G.numEdges;i++)	/* 循环每一条边 */
	{
		n=Find(parent,edges[i].begin);
		m=Find(parent,edges[i].end);
		if (n!=m) /* 假如n与m不等，说明此边没有与现有的生成树形成环路 */
		{
			parent[n]=m;	/* 将此边的结尾顶点放入下标为起点的parent中。 */
							/* 表示此顶点已经在生成树集合中 */
			cout<<"("<<edges[i].begin<<","<<edges[i].end<<") "<<edges[i].weight<<endl;
		}
	}
}

/* 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];
	for(v = 0; v<G.numVertexes; v++)
	{
		final[v] = 0;
		(*D)[v] = G.arc[V0][v];
		(*P)[v] = V0;
	}
	(*D)[V0] = 0;
	final[V0] = 1;
	/*开始主循环，每次求得V0到某个V顶点的最短路径*/
	for(v=0; v<V0; v++)
	{
		min = INFINITY;
		for(w=0; w<G.numVertexes; w++)
		{
			if(!final[w] && (*D)[w]<min)
			{
				k = w;
				min = (*D)[w];
			}
		}
		final[k] = 1;
		for (w=0; w<G.numVertexes; w++)		/*修正当前最短路径及距离*/
		{
			if(!final[w] && (min+G.arc[k][w]<(*D)[w]))
			{
				(*D)[w] = min+G.arc[k][w];
				(*P)[w] = k;
			}
		}
	}
	for(v=V0+1; v<G.numVertexes; v++)
	{
		min = INFINITY;
		for(w=0; w<G.numVertexes; w++)
		{
			if(!final[w] && (*D)[w]<min)
			{
				k = w;
				min = (*D)[w];
			}
		}
		final[k] = 1;
		for (w=0; w<G.numVertexes; w++)		/*修正当前最短路径及距离*/
		{
			if(!final[w] && (min+G.arc[k][w]<(*D)[w]))
			{
				(*D)[w] = min+G.arc[k][w];
				(*P)[w] = k;
			}
		}
	}

	cout<<"V"<<V0<<"节点到其余个节点的最短路径为："<<endl;
	for (w=0; w<G.numVertexes; w++)
	{
		cout<<(*D)[w]<<"  ";
	}
	cout<<endl;
	cout<<"V"<<V0<<"节点到其余个节点的最短路径的前驱节点为："<<endl;
	for (w=0; w<G.numVertexes; w++)
	{
		cout<<"V"<<(*P)[w]<<"  ";
	}
	cout<<endl;
}
/***********Dijkstra算法结束************/

/*Floyd算法，求网图G中各顶点V到其余顶点W最短路径P[V][W]及带权长度D[V][W]*/
void ShortestPath_Floyd(MGraph G, Pathmatrix *P, ShortPathTable_Floyd *D)
{
	int v,w,k;
	for(v=0; v<G.numVertexes; ++v)	/*初始化D与P*/
	{
		for(w=0; w<G.numVertexes; ++w)
		{
			(*D)[v][w] = G.arc[v][w];
			(*P)[v][w] = w;
		}
	}
	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])
				{
					(*D)[v][w] = (*D)[v][k]+(*D)[k][w];
					(*P)[v][w] = (*P)[v][k];
				}
			}
		}
	}

	for(v=0; v<G.numVertexes; ++v)	/*输出显示最短路径*/
	{
		for(w=v+1; w<G.numVertexes; w++)
		{
			cout<<"V"<<v<<"-V"<<w<<"的最短距离为："<<(*D)[v][w]<<endl;
			k = (*P)[v][w];
			cout<<"路径为：V"<<v;
			while(k!=w)
			{
				cout<<" -> V"<<k;
				k=(*P)[k][w];
			}
			cout<<" -> V"<<w<<endl;
		}
		cout<<endl;
	}
}
/***********Floyd算法结束************/

对于如下的图：

代码运行结果如下：

两算法结果一致。