• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

每对结点之间最短路径的C++实现

OC/C/C++ 水墨上仙 1443次浏览

Dijkstra算法和Bellman-Ford算法只能计算出起始点到其他各点的最短路径,但不能计算任意两队顶点之间的最短路径。若真想利用这两张算法,可以来一个循环,每次让不同的顶点成为起始顶点,这样也可以解决,但这种方法效率比较低,所以要想其他方法。
我们可以用最优化的原理来求每对顶点之间的最短路径,基本思想是:假设图中有一条从i到j结点的最短路径,k是图中的一点,那么i到j的路径有可能经过k,也有可能不经过k,因而i到j的最短路径是这两种情况中所需权值较小的那条路径,因而我们可以通过对k的迭代,求出任意一对结点之间的最短路径。
来源:http://blog.csdn.net/iqrocket/article/details/8307122

#include <iostream>
using namespace std;
const int MaxSize=10;
int arr[MaxSize][MaxSize]; //起始的邻接矩阵
int dist[MaxSize][MaxSize]; //保存每对结点之间的最短路径
int numNode=0;
//创建邻接矩阵
void createArr()
{
	cin>>numNode;
	for(int i=0;i<numNode;++i)
		for(int j=0;j<numNode;++j)
			cin>>arr[i][j];
}
//求出每对结点之间的最短路径
void allPath()
{
	//初始化dist数组
	for(int i=0;i<numNode;++i)
		for(int j=0;j<numNode;++j)
			dist[i][j]=arr[i][j];
	//迭代:对于结点k,若i直接到j的距离大于i经过k再到j的距离和时,
	//则改写i到j的距离
	for(int k=0;k<numNode;++k)
		for(int i=0;i<numNode;++i)
			for(int j=0;j<numNode;++j)
				if(dist[i][k]+dist[k][j]<dist[i][j])
					dist[i][j]=dist[i][k]+dist[k][j];
}
int main()
{
	createArr();
	allPath();
}


喜欢 (0)
加载中……