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

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

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

我们这时怎么做?

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

相关文章

来自专栏noteless

UML简单介绍-如何看懂UML(二)

你画了一个三角形说这是一个接口,我花了一个圆形,跟你讲这个是接口?这其中的问题不言而喻。

1672
来自专栏ATYUN订阅号

赫尔辛基大学AI基础教程:搜索和游戏(2.3节)

在本节中,我们将研究一个经典的AI问题:游戏。为了清晰起见,我们将重点关注的最简单的场景是双人游戏,如井字棋和国际象棋等完全信息游戏。

983
来自专栏null的专栏

优化算法——拟牛顿法之DFP算法

一、牛顿法    image.png image.png 二、DFP拟牛顿法 1、DFP拟牛顿法简介         DFP拟牛顿法也称为DFP校正方法,DFP...

3326
来自专栏C语言C++游戏编程

无形细节最为致命,C语言中与零值比较那些小事儿

无论是float还是double类型的变量,都有精度限制。所以一定要避免将浮点变量用“==”或“!=”与数字比较,应该设法转化成“>=”或“。小编给大家推荐一个...

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

洛谷P1720 月落乌啼算钱

目背景 (本道题目木有以藏歌曲……不用猜了……) 《爱与愁的故事第一弹·heartache》最终章。 吃完pizza,月落乌啼知道超出自己的预算了。为了不在爱与...

3179
来自专栏算法channel

AI 路上,第一步这么走下去...

算法是描述解决一个问题的步骤,外界给它所指定的数据,然后经过一系列步骤输出一个结果。为了更快更轻量级地解决问题,我们会选择高效精简的结构去实现,这种结构称为数据...

1266
来自专栏大数据文摘

数学菜鸟的AI学习攻略 | 数学符号轻松入门

3834
来自专栏小L的魔法馆

第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛--I-填空题

3455
来自专栏专知

【LeetCode】关关的刷题日记23——Leetcode 66. Plus One

关小刷刷题 23——Leetcode 66. Plus One 题目 Given a non-negative integer represented as a...

2933
来自专栏机器之心

机器学习时代的哈希算法,将如何更高效地索引数据

2535

扫码关注云+社区

领取腾讯云代金券