【算法导论】每对顶点之间的最短路径算法

简介:         对于一个顶点数为N的有向网路图,我们可以通过前面所提到的单源最短路径算法执行N次来获得每一对顶点间的最短路径。这种方法的时间复杂度为O(N*N*N)。

        对于一个顶点数为N的有向网路图,我们可以通过前面所提到的单源最短路径算法执行N次来获得每一对顶点间的最短路径。这种方法的时间复杂度为O(N*N*N)。如果网络中有负权值的边,则需要使用前面提到的单源最短路径算法之Bellman—Floyd算法。总之,总可以通过单源最短路径来求得每对顶点间的最短路径。这里我就不再用程序实现上述方法,下面介绍Floyd解决这一问题的另一种算法,它形式简单,利于理解,而且时间复杂度同样为O(N*N*N)。

       Floyd算法是根据给定有向网络的邻接矩阵dist[n][n]来求顶点vi到顶点vj的最短路径。这一算法的基本思想是:假设vi和vj之间存在一条路径,但这并不一定是最短路径,试着在vi和vj之间增加一个中间顶点vk。 若增加vk后的路径(vi, vk, vj) 比(vi, vj)短,则以新的路径代替原路径,并且修改dist[i][j]的值为新路径的权值;若增加vk后的路径比(vi, vj)更长,则维持dist[i][j]不变。然后在修改后的dist矩阵中,另选一个顶点作为中间顶点,重复以上的操作,直到除vi和vj顶点的其余顶点都做过中间顶点为止。下面以具体实例来说明问题:

假设有向网路图如下所示:


设原始的最短路径矩阵为L(1),经过一次循环后得到新的最短矩阵为L(2),依此类推,当得到L(N-1)时,我们就得到了最短的路径矩阵。最短路径矩阵的变化情况如下:


具体程序实现如下:

#include<stdio.h>

#define N 5 //顶点个数
#define MAX 10000

void Floyd(int dist[N][N],int A[N][N],int path[N][N])
{


	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			for(int k=0;k<N;k++)
			{
				/*if(A[i][j]>(A[i][k]+dist[k][j]))//方法一:计算每一次矩阵
				{
					A[i][j]=(A[i][k]+dist[k][j]);
					path[i][j]=path[k][j];
				}*/
				if(A[i][j]>(A[i][k]+A[k][j]))//方法二:计算2的幂次矩阵
				{
					A[i][j]=(A[i][k]+A[k][j]);
					path[i][j]=path[k][j];
				}
			}
}

void main()
{
	int dist[N][N]={{0,3,8,MAX,-4},//图的邻接矩阵
	                {MAX,0,MAX,1,7},
	                {MAX,4,0,MAX,MAX},
	                {2,MAX,-5,0,MAX},
	                {MAX,MAX,MAX,6,0}};
	int A[N][N];
	int path[N][N]={0};//给出两顶点间的路径
	int pre=0;

	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
		{
			A[i][j]=dist[i][j];
			if(dist[i][j]!=MAX)
				path[i][j]=i+1;
			else
				path[i][j]=0;
		}
	
	for(int k=0;k<2;k++)//若用方法一,需循环N-3次,若用方法二,需要循环lg(N-1)次
		Floyd(dist,A,path);

	printf("每对顶点间的最短路径矩阵为:\n");
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
			printf("%d ",A[i][j]);
		printf("\n");
	}
	printf("\n每对顶点的具体最短路径为:\n");
	
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			printf("%d: %d ",A[i][j],j+1);
		pre=path[i][j];
		while((pre!=0)&&(pre!=i+1))
		{
			printf("<- %d ",pre);
			pre=path[i][pre-1];
		}
		printf(" <- %d\n",i+1);
		}
	}
}

结果显示如下:



程序不但显示了两点之间的最短路径长度,而且显示了具体的路径。在程序中,我用了两种方法求最短路径矩阵,其中第二种方法更加简单的,因为我们要求的最短路径矩阵为L(N-1)。比如说当N=5时,我们需要最终得到L(4),我们可以只求L(1)、L(2)、L(4),而不需要求得每一个L。


注:如果程序出错,可能是使用的开发平台版本不同,请点击如下链接: 解释说明


原文:http://blog.csdn.net/tengweitw/article/details/17577623

作者:nineheadedbird


目录
相关文章
|
1月前
|
存储 算法 C语言
数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)
数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)
39 1
|
27天前
|
算法 Java
Java数据结构与算法:最短路径算法
Java数据结构与算法:最短路径算法
|
29天前
|
算法 Java 定位技术
Java数据结构与算法:贪心算法之最短路径
Java数据结构与算法:贪心算法之最短路径
|
1月前
|
算法 定位技术
探寻最短路径之谜:Dijkstra算法详解
探寻最短路径之谜:Dijkstra算法详解
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
|
2月前
|
算法 机器人 Python
Python实现教程:平面最短路径算法
Python实现教程:平面最短路径算法
40 1
|
2月前
|
算法
最短路径的两大算法
最短路径的两大算法
|
2月前
|
算法 定位技术 Windows
R语言最大流最小割定理和最短路径算法分析交通网络流量拥堵问题
R语言最大流最小割定理和最短路径算法分析交通网络流量拥堵问题
|
2月前
|
人工智能 算法
一些算法的复习(最短路径、最小生成树、dp)
一些算法的复习(最短路径、最小生成树、dp)
|
2月前
|
人工智能 算法 Java
【算法设计与分析】— —单源最短路径的贪心算法
【算法设计与分析】— —单源最短路径的贪心算法
51 0

热门文章

最新文章