蓝桥杯 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月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
97 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
2月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
4月前
|
算法
Floyd算法
Floyd算法
57 1
|
6月前
|
存储 机器学习/深度学习 算法
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
75 3
|
2月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
128 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
2月前
|
存储 算法 C++
弗洛伊德(Floyd)算法(C/C++)
弗洛伊德(Floyd)算法(C/C++)
|
4月前
|
算法 Java 测试技术
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
这篇文章介绍了基于动态规划法的三种算法:解决背包问题的递归和自底向上实现、Warshall算法和Floyd算法,并提供了它们的伪代码、Java源代码实现以及时间效率分析。
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
|
6月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
7月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
115 0
|
7月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
88 0

热门文章

最新文章