最短路径(一)——多源最短路径

引出问题:多源最短路径的问题

暑假,小文准备去一些城市旅游。为了节省经费以及方便计划旅程,小文希望知道任意两个城市之间的最短路径。假如有四个城市八条公路。

我们这时怎么做?

首先用一个数据结构来存储图的信息,因为是四个城市就可以选择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)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

OpenGLES进阶教程7-天空盒效果

教程 OpenGLES入门教程1-Tutorial01-GLKit OpenGLES入门教程2-Tutorial02-shader入门 OpenGLES入门...

3606
来自专栏新智元

Jeff Dean推荐:用TPU跑Julia程序,只需不到1000行代码

Julia是一门集众家所长的编程语言。随着Julia 1.0在8月初正式发布,Julia语言已然成为机器学习编程的新宠。

761
来自专栏数据结构与算法

HDU4576 Robot(概率)

抄袭自https://www.cnblogs.com/Paul-Guderian/p/7624039.html

641
来自专栏CSDN技术头条

数据可视化的10个关键术语

Format 交互方式 Interactive visualisations allow you to modify, manipulate and explo...

1767
来自专栏逍遥剑客的游戏开发

UE4衣服材质换色

3045
来自专栏我是业余自学C/C++的

图 原

图是有限集V和E的有序对,即G=(V,E)。其中V的元素称为顶点(也称为节点或点),E的元素称为边(也称为弧或线)。每一条边连接两个不同的顶点,而且用元组(i,...

742
来自专栏数据小魔方

think-cell chart系列5——堆积不等宽柱形图

今天要分享的是think-cell chart系列的第五篇——堆积不等宽柱形图。 其实要问我为什么对think-cell chart这么情有独钟,现在给出答案—...

3855
来自专栏HansBug's Lab

1632: [Usaco2007 Feb]Lilypad Pond

1632: [Usaco2007 Feb]Lilypad Pond Time Limit: 5 Sec  Memory Limit: 64 MB Submit:...

2758
来自专栏AI科技大本营的专栏

开启机器学习的第一课:用Pandas进行数据分析

翻译 | AI科技大本营 参与 | 林椿眄 本课程的目的并不是要开发一门全新的机器学习或数据分析的综合入门课程,也不是想借此来取代基础教育、在线/离线课程或一...

3745
来自专栏趣学算法

算法之美——魔鬼序列

假设第1个月有1对刚诞生的兔子,第2个月进入成熟期,第3个月开始生育兔子,而1对成熟的兔子每月会生1对兔子,兔子永不死去……那么,由1对初生兔子开始,12个月...

512

扫码关注云+社区