数学建模--最短路径算法的Python实现

目录

1.算法流程简介

2.算法核心代码

3.算法效果展示

1.算法流程简介

#最短路径算法
#针对有向图的最短路径问题,我们有很多的算法能解决.
"""
目前主流算法如下所示:
Dijkstra算法:Dijkstra算法是一种单源最短路径算法,用于计算从起点到其它所有节点的最短路径。该算法的基本思想是从起点开始,依次计算每个节点到起点的最短路径,然后再依次计算每个节点到起点的最短路径,直到所有节点都被计算完毕。。
Ford算法:Ford算法是一种动态规划算法,用于找到带权重的有向图中从一个起点到所有其他节点的最短路径。该算法可以处理负边权图,并且还可以检测到负权环。
Floyd-Warshall算法:Floyd-Warshall算法是一种动态规划算法,用于找到带权重的有向图中任意两个节点之间的最短路径。该算法可以处理负边权图,并且可以同时计算多组最短路径。
"""
"""
#在python中,我们能够借用networkx库中的函数来进行最短路径的求解
如下所示:networks_shortest_path(G,source,target,weight,method)函数如下所示:
networkx.shortest_path(G, source=None, target=None, weight=None, method='dijkstra')
1.G代表图矩阵,可以是无向或者有向
2.source代表的是起始点
3.target代表的是终止点
4.weight代表的边与边之间的权重关系
5.method表示所用的算法,默认为Dijkstra,也可以指定Bellman-Ford和Floyd-Warshall。
#ps1:该算法返回值是一个字典,键表示的是目标结点,值表示最短路径
#ps2:如果需要求最短的距离,请使用networks_short_path_length()
"""
具体流程步骤:
#1.导入各边距离权重矩阵
#2.将矩阵进行转化
#3.求解任意点的最短路径问题,以A点为例

2.算法核心代码

import networkx as nx
#1.导入各边距离权重矩阵
number=6#gragh中参与计算的点的数量
dis = [[0, 50, 0, 40, 25, 10],[50, 0, 15, 20, 0, 25],[0, 15, 0, 10, 20, 0],[40, 20, 10, 0, 10, 25],[25, 0, 20, 10, 0, 55],[10, 25, 0, 25, 55, 0]]
#2.将矩阵进行转化
G=nx.DiGraph()
for i in range(number):for j in range(number):if dis[i][j]!=0:#可以处理负权G.add_edge(chr(i+65),chr(j+65),weight=dis[i][j])
#3.求解任意点的最短路径问题,以A点为例
best_path = nx.shortest_path(G, source='A', weight='weight') 
best_path_length = nx.shortest_path_length(G, source='A', weight='weight')#答案存在这里   
for loc,cost in best_path_length.items():print("从A到",str(loc),"的最短路径是",str(best_path[loc]),"票价为"+str(cost)+"元")

3.算法效果展示

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/121562.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

java八股文面试[多线程]——线程间通信方式

多个线程在并发执行的时候,他们在CPU中是随机切换执行的,这个时候我们想多个线程一起来完成一件任务,这个时候我们就需要线程之间的通信了,多个线程一起来完成一个任务,线程通信一般有4种方式: 通过 volat…

TypeScript_树结构-BST树

树结构 树的特点 树通常有一个根。连接着根的是树干树干到上面之后会进行分叉成树枝,树枝还会分又成更小的树枝在树枝的最后是叶子 树的抽象 树可以模拟生活中的很多场景,比如:公司组织架构、家谱、DOM Tree、电脑文件夹架构 优秀的哈希函…

STM32 SPI对存储芯片发送写是能命令后一直忙等待

我采用CUBE配置的SPI外设,对NSS引脚选择了硬件输出,这种方式对读取命令没有影响,但是对写命令有,当我发送写是能命令后,读取状态寄存器的值一直都是忙,我猜测这可能是硬件控制NSS引脚后,对于HAL…

如何用Jmeter编写脚本压测?

随着商业业务不断扩张,调用adsearch服务频率越来越高,所以这次想做个压测,了解目前多少并发量可以到达adsearch服务的界值。 这次选用的jmeter压测工具,压测思路如图: 一、日志入参 日志选取的adsearch 的 getads部分…

WEB APIs day6

一、正则表达式 RegExp是正则表达式的意思 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" co…

二叉树的介绍及二叉树的链式结构的实现(C语言版)

前言 二叉树是一种特殊的树&#xff0c;它最大的度为2&#xff0c;每个节点至多只有两个子树。它是一种基础的数据结构&#xff0c;后面很多重要的数据结构都是依靠它来进行实现的。了解并且掌握它是很重要的。 目录 1.二叉树的介绍 1.1概念 1.2现实中的二叉树 1.3特殊的二叉…

QCAD for Mac免费下载:卓越的2D辅助设计工具

QCAD是一款功能强大的2D辅助设计画图软件&#xff0c;现已适配Mac系统&#xff0c;为Mac用户提供了便捷高效的设计工具。 QCAD提供了丰富的绘图功能&#xff0c;可以轻松绘制各种平面图形&#xff0c;包括直线、圆、椭圆、弧线等。 同时&#xff0c;QCAD还支持多种绘图工具&am…

树莓 LUMA-OLED.EXAMPLE使用

详细介绍在文件目录下的README.rst中 第一步 $ sudo usermod -a -G i2c,spi,gpio pi //好像没什么用 $ sudo apt install python3-dev python3-pip python3-numpy libfreetype6-dev libjpeg-dev build-essential //安装依赖包&#xff0c;树莓派中好像已经有了 $ sudo a…

linux信号量

通过学习linux的信号量&#xff0c;对linux的信号量进行了编程。

iPhone 15 Pro展示设计:7项全新变化呈现

我们不应该再等iPhone 15 Pro在苹果9月12日的“Wonderlust”活动上发布了&#xff0c;而且可能会有很多升级。有传言称&#xff0c;iPhone 15 Pro将是自iPhone X以来最大的飞跃&#xff0c;这要归功于大量的新变化&#xff0c;从带有更薄边框的新钛框架到顶级A17仿生芯片和动作…

Burp插件HaE与Authz用法

HaE与Authz均为BurpSuite插件生态的一员&#xff0c;两者搭配可以避免“越权”、“未授权”两类漏洞的重复测试行为。&#xff08;适用于业务繁杂&#xff0c;系统模块功能多的场景&#xff09; 两个插件都可以在store里安装 安装完后&#xff0c;点击Filter Settings勾选Sho…

构建稳定的爬虫系统:如何选择合适的HTTP代理服务商

在构建一个稳定、高效的爬虫系统中&#xff0c;选择合适的HTTP代理服务商是至关重要的一步。本文将介绍如何选取可靠且性能优秀的HTTP代理服务供应商&#xff0c;来完成搭建一个强大而稳定的爬虫系统。 1.了解不同类型和特点 -免费公开代理服务器:提供免费但可能存在限制或不…

整数拆分【动态规划】

整数拆分 给定一个正整数 n &#xff0c;将其拆分为 k 个 正整数 的和&#xff08; k > 2 &#xff09;&#xff0c;并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 class Solution {public int integerBreak(int n) {int[] dp new int[n 1];//正整数&#x…

mysql数据库使用技巧整理

查看当前数据库已建立的client连接 > SHOW VARIABLES LIKE max_connections; -- 查看数据库允许的最大连接数&#xff0c;不是实时正在使用的连接数 > SHOW STATUS LIKE Threads_connected; -- 查看当前数据库client的连接数 > SHOW PROCESSLIST; -- 查看具体的连接

【jsvue】联合gtp仿写一个简单的vue框架,以此深度学习JavaScript

用 gtp 学习 Vue 生命周期的原理 lifecycle.js function Vue(options) {// 将选项保存到实例的 $options 属性中this.$options options;// 若存在 beforeCreate 钩子函数&#xff0c;则调用之if (typeof options.beforeCreate function) {options.beforeCreate.call(this);…

类和对象(中)

&#x1f493;博主个人主页:不是笨小孩&#x1f440; ⏩专栏分类:数据结构与算法&#x1f440; C&#x1f440; 刷题专栏&#x1f440; C语言&#x1f440; &#x1f69a;代码仓库:笨小孩的代码库&#x1f440; ⏩社区&#xff1a;不是笨小孩&#x1f440; &#x1f339;欢迎大…

vs2008下的mfc hello world实现

笔者不知道会写这种博文&#xff0c;好久没写mfc程序&#xff0c;hello world都不会创建了。起因是来了个mfc任务&#xff0c;那就得把mfc熟悉起来&#xff0c;先看下实现效果吧 因为是基于2008的&#xff0c;那就按照2008创建吧 文章目录 第一步&#xff1a;文件新建项目第二…

【二等奖方案】大规模金融图数据中异常风险行为模式挖掘赛题「冀科数字」解题思路

第十届CCF大数据与计算智能大赛&#xff08;2022 CCF BDCI&#xff09;已圆满结束&#xff0c;大赛官方竞赛平台DataFountain&#xff08;简称DF平台&#xff09;正在陆续释出各赛题获奖队伍的方案思路&#xff0c;欢迎广大数据科学家交流讨论。 本方案为【大规模金融图数据中…

CS420 课程笔记 P4 - 以16进制形态编辑游戏文件

文章目录 IntroductionFinding save filesStringsUnicodeExample!Value searchHealth searchConclusion Introduction 这节课我们将学习编辑十六进制&#xff0c;主要用于编辑保存文件&#xff0c;但十六进制编辑涉及的技能可以很好地转移到&#xff1a; Save file editingRe…

python数据分析基础—取某列字符的前几个字符

文章目录 前言取某列前几个字符方法一&#xff1a;[x[:7] for x in data["calling_nbr"]]方法二&#xff1a;data[calling_nbr].str[:7] 前言 在进行数据分析时&#xff0c;有时候我们需要提取单列的前几个字符串进行分析。本文主要讲述针对这种情况处理方法。 取某…