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

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

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

我们这时怎么做?

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

相关文章

来自专栏Crossin的编程教室

一个略奇葩的计算圆周率的程序

某天早上,在去上班的地铁上,突然莫名地想起有个“投针实验”,于是就心血来潮想写个小程序试验一下。 关于具体描述,可以去搜索“布丰投针实验”。简单来说,就是: 假...

3099
来自专栏申龙斌的程序人生

零基础学编程037:小数据分析

R语言内置强大的向量运算,是搞数据分析的强大的编程语言,而Python也毫不逊色。今天就试着分析一下考试成绩表中两门科目的相关性。 问题描述: 有一个CSV文件...

3229
来自专栏工科狗和生物喵

【机器视觉与图像处理】基于MATLAB的角度计算

我一开始还苦思冥想,不知道怎么才能提取出来这个因素,所以很是烦恼不知道该如何是好,但是昨天看了下群里面的说法,我瞬间就理通了。只要转变下思维,把图像看成一个二维...

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

AI 技术讲座精选:深度拼写——重新认识21世纪的拼写校正程序

本文是一篇关于工程学的内容,讲述的是当前较先进的技术——拼写校对程序。这项技术的用处就是让低级工程师使用起来得心应手。 许多年前,我根据Peter Norvig...

2678
来自专栏数据派THU

独家 | 带你入门比Python更高效的Numpy(附代码)

向量化技巧对于数据科学家来说是相当熟知的,并且常用于编程中,以加速整体数据转换,其中简单的数学变化通过可迭代对象(例如列表)执行。未受到重视的是,把有一定规模的...

823
来自专栏林欣哲

自然语言处理--文本处理

自然语言处理的目的是让机器试图理解和处理人类的文字。通常来说,人的语言是冗余的,含有歧义的,而机器是准确的,无歧义的,要让机器理解,这之间存在一个转换的问题。 ...

3268
来自专栏钱塘大数据

AI系统首次实现自主编程,完爆初级程序员!

作者:THU数据派 让AI自动编程是人工智能领域长久以来的梦想之一。现在,来自彭博和英特尔实验室的两位研究人员,号称实现了首个能够自动生成完整软件程序的AI系...

2809
来自专栏PPV课数据科学社区

用 Python 做文本挖掘的流程

作者:肖智博 来源:https://zhuanlan.zhihu.com/p/19630762 点击阅读原文可进入超链接。 收集数据 数据集。如果是已经被人做...

4038
来自专栏用户2442861的专栏

kaggle-2美国人口普查年收入50K分类

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

853
来自专栏hanlp学习笔记

Java中文分词hanlp使用

github地址:https://github.com/hankcs/HanLP

500

扫码关注云+社区