引出问题：多源最短路径的问题
暑假，小文准备去一些城市旅游。为了节省经费以及方便计划旅程，小文希望知道随意两个城市之间的最短路径。
假如有四个城市八条公路。
我们这时怎么做？
首先用一个数据结构来存储图的信息，由于是四个城市就能够选择4*4的矩阵：
| 距离 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 2 | 6 | 4 |
| 2 | ∞ | 0 | 3 | ∞ |
| 3 | 7 | ∞ | 0 | 1 |
| 4 | 5 | ∞ | 12 | 0 |
这时我们怎么做呢？
首先想到了两个指定点的最短路径问题。所以进行n2遍深度或者广度优先搜索。既能够得到终于结果。但别的方法呢？
如果如今仅仅同意经过1号顶点，求随意两点间的最短距离。程序例如以下：
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++){if (e[i][j] > e[i][1] + e[1][j])e[i][j] = e[i][1] + e[1][j]}
}这事实上是一种“动态规划”的思想，从i顶点到j号顶点仅仅经过前K号点的最短路程，以下给出算法的完整代码：
#include <stdio.h>
int main()
{int e[10][10],k,i,j,n,m,t1,t2,t3int inf=99999;//n表示顶点个数，m表示边的条数scanf("%d %d",&n,&m)//初始化for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i=j) e[i][j]=0 //e[i][j]表示的是从i顶点到j顶点之间的路程else e[i][j]=inf;//读入边for(i=1;i<=m;i++){scanf("%d %d %d",&t1,&t2,&t3);e[t1][t2]=t3;}//算法核心语句for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(e[i][j]>e[i][k]+e[k][j])e[i][j] = e[i][k]+e[k][j];//输出终于结果for(i=1;i<=n;i++){for(j=1;j<=n;j++){printf("%10d",e[i][j]);}printf("\n");}return 0;
}通过这样的算法能够求出随意两点之间的最短路径，时间复杂度为O（N3）