最短路径（一）——多源最短路径
引出问题：多源最短路径的问题
暑假，小文准备去一些城市旅游。为了节省经费以及方便计划旅程，小文希望知道任意两个城市之间的最短路径。假如有四个城市八条公路。
我们这时怎么做？
首先用一个数据结构来存储图的信息，因为是四个城市就可以选择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,t3
int 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）
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016年03月11日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读