Dijkstra算法和Bellman-Ford算法只能计算出起始点到其他各点的最短路径，但不能计算任意两队顶点之间的最短路径。若真想利用这两张算法，可以来一个循环，每次让不同的顶点成为起始顶点，这样也可以解决，但这种方法效率比较低，所以要想其他方法。
我们可以用最优化的原理来求每对顶点之间的最短路径，基本思想是：假设图中有一条从i到j结点的最短路径，k是图中的一点，那么i到j的路径有可能经过k，也有可能不经过k，因而i到j的最短路径是这两种情况中所需权值较小的那条路径，因而我们可以通过对k的迭代，求出任意一对结点之间的最短路径。
|
#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();
} |
