上图中有 4 个城市 8 条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程，也就是求任意两个点之间的最短路径。

当任意两点之间不允许经过第三个点时，这些城市之间最短路程就是初始路程，如下。

在只允许经过 1 号顶点的情况下，任意两点之间的最短路程更新为：

在只允许经过 1 和 2 号顶点的情况下，任意两点之间的最短路程更新为：

同理，继续在只允许经过 1、2 和 3 号顶点进行中转的情况下，求任意两点之间的最短路程。任意两点之间的最短路程更新为：

最后允许通过所有顶点作为中转，任意两点之间最终的最短路程为：

核心代码

	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(e[i][j]>e[i][k]+e[k][j])
				e[i][j]=e[i][k]+e[k][j];

基本思想：最开始只允许经过 1 号顶点进行中转，接下来只允许经过 1 和 2 号顶点进行中转……允许经过 1~n 号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从 i 号顶点到 j 号顶点只经过前k号点的最短路程。
下面给出这个算法的完整代码：

#include<iostream>
using namespace std;
int main()
{
	int e[101][101];
	int n,m;
	int a,b,c;
	cin>>n>>m;
	//数组初始化 
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==j)
				e[i][j]=0;
			else
				e[i][j]=99999999;
		}
	}
	//初始化各顶点之间的权值 
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		e[a][b]=c;
	}
	//核心算法 
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(e[i][j]>e[i][k]+e[k][j])
				e[i][j]=e[i][k]+e[k][j];
				
	cout<<endl;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<e[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

任意两点之间最终的最短路程如下：