蓝桥杯 floyd算法练习 最短路

简介: 蓝桥杯 floyd算法练习 最短路

问题描述:

image.png

看这个问题之前可以先看看这个这个up主讲的 很详细😀(有助于对下面核心代码的理解)


求最短路径Floyd算法!_哔哩哔哩_bilibili

https://www.bilibili.com/video/BV14R4y1x7GB


问题分析:我的难点就在于数据初始化 由于这是个无向图


那么必有graph[i][j]=graph[j][i]


即临接矩阵对称


然后我是手动输入的= =输了大概快7—8分钟


然后总结了下面几点规律:


对于无向图求最短路径 先把图标上箭头转化为有向图


权值用数字标出


每个地点用数字标出


最后利用对称的性质 大概可以把输入数据的时间缩小到5分钟左右


再其次就是floyd的算法 三行经典代码 今天算是体会到了


image.png


datas=[
    [0,0,0],
    [0,1,2],
    [0,2,1],
    [0,3,1],
    [0,4,1],
    [1,1,0],
    [1,0,2],
    [1,6,1],
    [1,9,2],
    [2,2,0],
    [2,0,1],
    [2,3,3],
    [2,5,3],
    [2,6,3],
    [3,3,0],
    [3,0,1],
    [3,4,1],
    [3,8,2],
    [3,6,2],
    [4,4,0],
    [4,0,1],
    [4,3,1],
    [4,7,1],
    [4,8,3],
    [5,5,0],
    [5,2,3],
    [5,6,1],
    [5,9,1],
    [6,6,0],
    [6,1,1],
    [6,2,3],
    [6,3,2],
    [6,10,2],
    [6,8,2],
    [6,5,1],
    [7,7,0],
    [7,3,1],
    [7,4,1],
    [7,8,1],
    [7,11,2],
    [8,8,0],
    [8,3,2],
    [8,4,3],
    [8,12,3],
    [8,7,1],
    [9,9,0],
    [9,1,2],
    [9,5,1],
    [9,18,2],
    [10,10,0],
    [10,6,2],
    [10,11,3],
    [10,13,1],
    [10,15,2],
    [11,11,0],
    [11,10,3],
    [11,7,2],
    [11,12,1],
    [11,17,1],
    [12,12,0],
    [12,8,3],
    [12,11,1],
    [12,13,2],
    [12,10,1],
    [12,18,1],
    [13,13,0],
    [13,10,1],
    [13,12,2],
    [13,15,1],
    [14,14,0],
    [14,16,1],
    [14,15,1],
    [14,17,3],
    [15,15,0],
    [15,14,1],
    [15,10,2],
    [15,13,1],
    [16,16,0],
    [16,12,1],
    [16,14,1],
    [17,17,0],
    [17,11,1],
    [17,14,3],
    [17,18,1],
    [18,18,0],
    [18,17,1],
    [18,9,2],
    [18,12,1]
]
graph=[[float('inf')]*19 for i in range(19)]
for u,v,c in datas:
    graph[u][v]=c
for k in range(19):#以k为中转站
    for i in range(19):
        for j in range(19):
            graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j])
print(graph[0][18])


这是我一开始的做法,比较笨 比如输入了[11,12,1],实际上[12,11,1]就不用在输入了


我们只需要在最外层循环补上graph[v][u]=c即可 答案是6


               题目链接最短路传送门


特别感谢以下这位博主的讲解 强推! 很适合和小郑一样刚入门的去看 真的很OK!

floyd算法(多源最短路径) python实现_Aiven-CSDN博客_floyd算法python代码

https://blog.csdn.net/AivenZhong/article/details/93770197?ops_request_misc=%257B%2522request%2


目录
相关文章
|
2月前
|
算法
Floyd算法
Floyd算法
33 1
|
4月前
|
存储 机器学习/深度学习 算法
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
42 3
|
2天前
|
存储 算法 C++
弗洛伊德(Floyd)算法(C/C++)
弗洛伊德(Floyd)算法(C/C++)
|
2天前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
2月前
|
算法 Java 测试技术
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
这篇文章介绍了基于动态规划法的三种算法:解决背包问题的递归和自底向上实现、Warshall算法和Floyd算法,并提供了它们的伪代码、Java源代码实现以及时间效率分析。
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
|
4月前
|
存储 算法 C语言
数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)
数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)
62 1
|
5月前
|
存储 算法 Java
蓝桥杯递归算法
蓝桥杯中的递归算法涉及将问题分解为子问题,通过函数自身调用来求解。优点是简洁易懂,但效率低且可能引发栈溢出。示例包括:数组求和、数的阶乘、斐波那契数列及最大公约数计算,以及字符串翻转。代码展示了各种递归场景的Java实现,如`f3`计算数组和,`f`求阶乘,`f1`计算斐波那契数,`f2`找最大公约数,和`f1`字符串反转。
33 1
|
4月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
3天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA遗传优化的GroupCNN分组卷积网络时间序列预测算法matlab仿真
该算法结合了遗传算法(GA)与分组卷积神经网络(GroupCNN),利用GA优化GroupCNN的网络结构和超参数,提升时间序列预测精度与效率。遗传算法通过模拟自然选择过程中的选择、交叉和变异操作寻找最优解;分组卷积则有效减少了计算成本和参数数量。本项目使用MATLAB2022A实现,并提供完整代码及视频教程。注意:展示图含水印,完整程序运行无水印。
|
1天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。