百度360必应搜狗淘宝本站头条
nodejsbufferorg.jsoupsetnocountoncv2.bitwise_nottime.strptime
当前位置：网站首页 > 编程字典 > 正文

Python数学建模系列(八)图论

toyiye 2024-06-21 12:25 12 浏览 0 评论

菜鸟学习记：第四十九天

劳逸结合

到处走走

开拓视野

若数学公式未显示或显示不正确 可以查看 Python数学建模系列（八）：图论

前言

?

Hello！小伙伴！

非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～

自我介绍 「?(?ˊ?ˋ)?」

昵称：海轰

标签：程序猿｜C++选手｜学生

简介：因C语言结识编程，随后转入计算机专业，有幸拿过一些国奖、省奖...已保研。目前正在学习C++/Linux/Python

学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！ 初学Python 小白阶段

文章仅作为自己的学习笔记 用于知识体系建立以及复习

题不在多 学一题 懂一题

知其然 知其所以然！

?

1 图论模型 - Dijkstra

Dijkstra算法能求一个顶点到另一顶点最短路径。

基础概念

  • 无向图： 若图中的每条边都是没有方向的，则称该图为无向图。
  • 有向图： 若图中的每条边都是有方向的，则称该图为有向图。
  • 混合图： 若图中的部分边是有方向的，而部分边是无方向的，则称该图为混合图。

样例1

如下图所示，我们需要从①点走到⑨点，每条边的红色数 字代表这条边的长度，我们如何找到①到⑨的最短路径呢？

步骤：

  1. 将①标记为P，其它标记为T，找出从①出发当前最短的边所到的点，将该点的T改为P
  2. 将所有P点找到可以到达的T标记点上最短的边，将到达的点T改为P
  3. 重复步骤，指导终点的T变为P

过程展示：圈加数字代表每个顶点，()内数字代表当前行走的距离

?

1.①(0)

2.①②(1)

3.①②⑤(3)

4.①②⑤(3) ①④(3)

5.①②⑤⑦(5) ①④(3)

6.①②⑤⑦⑥(6) ①④(3)

7.①②⑤⑦⑥(6) ①②⑤③(6) ①④(3)

8.①②⑤⑦⑥(6) ①②⑤③④(7) ①④(3)

9.①②⑤⑦⑥⑧(8) ①②⑤③④(7) ①④(3)

10.①②⑤⑦⑥⑧(8) ①②⑤⑦⑨(8) ①②⑤③④(7) ①④(3)

?

「所以最短的路径是 ① ② ⑤ ⑦ ⑨， 长度为8」

带权邻接矩阵： 带权邻接矩阵是表示顶点相邻关系的矩阵，例如上面那个图的带权邻接矩阵如下

?

注意：原PPT中有错误， 点9 -> 点7 应该为inf （上图已经修改）

?

每个点和自己的距离为0（主对角线上元素都是零）

在图上相邻两个点的如果是连通的，距离就是矩阵的值，无向 的关于主对角线对称；有向的只有可以过去的路有数值

无法连通的距离就是无穷，记为inf

Demo代码

# 运行环境：Vs Code
# PPT中代码有点错误 已经修改～ 
# 以下代码经测试 可行
from collections import defaultdict 
from heapq import * 
inf = 99999 # 不连通值 
mtx_graph = [[0, 1, inf, 3, inf, inf, inf, inf, inf],
             [1, 0, 5, inf, 2, inf, inf, inf, inf],
             [inf, inf, 0, 1, inf, 6, inf, inf, inf],
             [inf, inf, inf, 0, inf, 7, inf, 9, inf],
             [inf, 2, 3, inf, 0, 4, 2, inf, 8],
             [inf, inf, 6, 7, inf, 0, inf, 2, inf],
             [inf, inf, inf, inf, inf, 1, 0, inf, 3],
             [inf, inf, inf, inf, inf, inf, 1, 0, 2], 
             [inf, inf, inf, inf, 8, inf, inf, 2, 0]]
m_n = len(mtx_graph)#带权连接矩阵的阶数 
edges = [] #保存连通的两个点之间的距离(点A、点B、距离) 
for i in range(m_n): 
    for j in range(m_n): 
        if i!=j and mtx_graph[i][j]!=inf: 
            edges.append((i,j,mtx_graph[i][j])) 

def dijkstra(edges, from_node, to_node): 
    go_path = [] 
    to_node = to_node-1 
    g = defaultdict(list) 
    for l,r,c in edges:
        # l:点A r:点B c:距离 
        # 字典： 点A -> (距离，点B)
        g[l].append((c,r)) 
    q, seen = [(0, from_node-1, ())], set()
    while q: 
        (cost, v1, path) = heappop(q)#堆弹出当前路径最小成本 
        if v1 not in seen: 
            seen.add(v1) 
            path = (v1, path) 
            if v1 == to_node: 
                break 
            for c, v2 in g.get(v1, ()): 
                if v2 not in seen: 
                    heappush(q, (cost+c, v2, path)) 
                
    if v1!=to_node:   #无法到达 
        return float('inf'), []
    if len(path)>0: 
        left=path[0] 
        go_path.append(left) 
        right=path[1] 
        while len(right)>0: 
            left=right[0] 
            go_path.append(left) 
            right=right[1] 
            
        go_path.reverse() #逆序变换 
        for i in range(len(go_path)): #标号加1 
            go_path[i]=go_path[i]+1 
    return cost, go_path 
leght, path = dijkstra(edges, 1, 9) 
print('最短距离为：'+str(leght)) 
print('前进路径为：'+str(path))

运行结果

最短距离为：8
前进路径为：[1, 2, 5, 7, 9]


2 图论模型-Floyd

Floyd算法通过动态规划解决任意两点间的最短路径（多源最短路径）的问题，「可以正确处理负权的最短路径问题」

关键原理：

?

枚举中间点k，找到最小的，作为的最小值

?

关键结论：

?

假设i和j之间的最短路径上的结点集里(不包含i，j)，编号最大的一个是x.那么在外循环k = x时， 肯定得到了最小值.

?

强归纳法 :

?

设i到x中间编号最大的是x1，x到j中间编号最大的是x2.由于x是i到j中间编号最大的，那么显然

?

根据结论，时候已经取得最小值，时候已经取得最 小值

那么时，和已经都取得最小值.

因此时，执行得

样例2

与样例1相似，只是这次我们「求出从每一个点到其他点的最短距离和路径」，每条边的红色数字代表这条边的长度。


Demo代码

from collections import defaultdict 
from heapq import * 
import numpy as np
inf = 99999 # 不连通值 
mtx_graph = [[0, 1, inf, 3, inf, inf, inf, inf, inf],
             [1, 0, 5, inf, 2, inf, inf, inf, inf],
             [inf, inf, 0, 1, inf, 6, inf, inf, inf],
             [inf, inf, inf, 0, inf, 7, inf, 9, inf],
             [inf, 2, 3, inf, 0, 4, 2, inf, 8],
             [inf, inf, 6, 7, inf, 0, inf, 2, inf],
             [inf, inf, inf, inf, inf, 1, 0, inf, 3],
             [inf, inf, inf, inf, inf, inf, 1, 0, 2], 
             [inf, inf, inf, inf, 8, inf, inf, 2, 0]]
def Floyd(graph): 
    N=len(graph) 
    A=np.array(graph)
    path=np.zeros((N,N)) 
    for i in range(0,N): 
        for j in range(0,N): 
            if A[i][j]!=inf: 
                path[i][j]=j 
    for k in range(0,N): 
        for i in range(0,N): 
            for j in range(0,N):
                # 原PPT这一句代码有错 写成了 A[i][j]+A[k][j]<A[i][j]
                # 正确应该是：A[i][k]+A[k][j]<A[i][j]
                if A[i][k]+A[k][j]<A[i][j]: 
                    A[i][j]=A[i][k]+A[k][j] 
                    path[i][j]=path[i][k]
    for i in range(0,N): 
        for j in range(0,N): 
            path[i][j]=path[i][j]+1 
    print('距离 = ') 
    print(A) 
    print('路径 = ') 
    print(path) 

Floyd(mtx_graph)

运行结果


?

注意：原PPT 结果中 最后一行又错 应该是 5. 5. 8. 8. 5. 8. 8. 8. 9. PPT中是： 5. 5. 7.7. 5. 7. 7. 8. 9. 因为在最初的 mtx_graph 设置就错了：点9到点7 应该是inf 而不是 3

?

结论：

  • 从点1 到 点9 的距离为8（结果中“距离”矩阵中第一行第九列数值）
  • 路径为【1 - 2 - 5 - 7 - 9】

怎么看路径呢？

  • 从最后结果中查看”路径“矩阵
  • 点1 到 点9 首先看第一行第九列 数值为2
  • 这是中间位置2，再看第二行第九列，数值为5
  • 再看第五行第九列，数值为7
  • 再看第七行第九列，数值为9
  • 得到最终路径【1 - 2 - 5 - 7 - 9】


3 机场航线设计

数据集来自航空业，有一些关于航线的基本信息。有某段旅程的起始点和目的地。还有一些列表示每段旅程的到达和起飞时间。这个数据集非常适合作为图进行分析。想象一下通过航线（边）连接的几个城市（节点）。

如果你是航空公司，你可以问如下几个问题：

  • 从A到B的最短途径是什么？分别从距离和时间角度考虑。
  • 有没有办法从C到D？
  • 哪些机场的交通最繁忙？
  • 哪个机场位于大多数其他机场“之间”？这样它就可以变成当地的一个中转站。

0、Airlines.csv数据

在这里插入图片描述

1、数据导入、观察变量 

import numpy as np 
import pandas as pd 
data = pd.read_csv('../Profile/Airlines.csv') 
data.shape #数据大小 

# (100, 16) 100行16列

运行结果

「查看各个变量的类型」

data.dtypes # 各变量的类型

运行结果

在这里插入图片描述

2、数据清洗

#将sched_dep_time转换为'std'—预定的出发时间 
data['std'] = data.sched_dep_time.astype(str).str.replace('(\d{2}$)', '') + ':' + data.sched_dep_time.astype(str).str.extract('(\d{2}$)', expand=False) + ':00'
 
#将sched_arr_time转换为“sta”—预定到达时间
data['sta'] = data.sched_arr_time.astype(str).str.replace('(\d{2}$)', '') + ':' + data.sched_arr_time.astype(str).str.extract('(\d{2}$)', expand=False) + ':00'
 
#将dep_time转换为'atd' -实际出发时间 
data['atd'] = data.dep_time.fillna(0).astype(np.int64).astype(str).str.replace('(\d{2}$)', '') + ':' + data.dep_time.fillna(0).astype(np.int64).astype(str).str.extract('(\d{2}$)', expand=False) + ':00'
 
#将arr_time转换为'ata' -实际到达时间
data['ata'] = data.arr_time.fillna(0).astype(np.int64).astype(str).str.replace('(\d{2}$)', '') + ':' + data.arr_time.fillna(0).astype(np.int64).astype(str).str.extract('(\d{2}$)', expand=False) + ':00'

3、时间信息合并

data['date'] = pd.to_datetime(data[['year', 'month', 'day']]) 
data = data.drop(columns = ['year', 'month', 'day'])

4、创建图

import networkx as nx
 
FG = nx.from_pandas_edgelist(data, source='origin', target='dest', edge_attr=True,)
# 查看所有节点 
FG.nodes()

运行结果

#NodeView(('EWR', 'MEM', 'LGA', 'FLL', 'SEA', 'JFK', 'DEN', 'ORD', 'MIA', 'PBI', 'MCO', 'CMH', 'MSP', 'IAD', 'CLT', 'TPA', 'DCA', 'SJU', 'ATL', 'BHM', 'SRQ', 'MSY', 'DTW', 'LAX', 'JAX', 'RDU', 'MDW', 'DFW', 'IAH', 'SFO', 'STL', 'CVG', 'IND', 'RSW', 'BOS', 'CLE'))

「查询图中的所有边」

# 查看所有边 
FG.edges()

运行结果

#EdgeView([('EWR', 'MEM'), ('EWR', 'SEA'), ('EWR', 'MIA'), ('EWR', 'ORD'), ('EWR', 'MSP'), ('EWR', 'TPA'), ('EWR', 'MSY'), ('EWR', 'DFW'), ('EWR', 'IAH'), ('EWR', 'SFO'), ('EWR', 'CVG'), ('EWR', 'IND'), ('EWR', 'RDU'), ('EWR', 'IAD'), ('EWR', 'RSW'), ('EWR', 'BOS'), ('EWR', 'PBI'), ('EWR', 'LAX'), ('EWR', 'MCO'), ('EWR', 'SJU'), ('LGA', 'FLL'), ('LGA', 'ORD'), ('LGA', 'PBI'), ('LGA', 'CMH'), ('LGA', 'IAD'), ('LGA', 'CLT'), ('LGA', 'MIA'), ('LGA', 'DCA'), ('LGA', 'BHM'), ('LGA', 'RDU'), ('LGA', 'ATL'), ('LGA', 'TPA'), ('LGA', 'MDW'), ('LGA', 'DEN'), ('LGA', 'MSP'), ('LGA', 'DTW'), ('LGA', 'STL'), ('LGA', 'MCO'), ('LGA', 'CVG'), ('LGA', 'IAH'), ('FLL', 'JFK'), ('SEA', 'JFK'), ('JFK', 'DEN'), ('JFK', 'MCO'), ('JFK', 'TPA'), ('JFK', 'SJU'), ('JFK', 'ATL'), ('JFK', 'SRQ'), ('JFK', 'DCA'), ('JFK', 'DTW'), ('JFK', 'LAX'), ('JFK', 'JAX'), ('JFK', 'CLT'), ('JFK', 'PBI'), ('JFK', 'CLE'), ('JFK', 'IAD'), ('JFK', 'BOS')])

在这里插入图片描述

「计算图的平均边密度」

#注意我们的100行数据都来自3个机场
nx.draw_networkx(FG, with_labels=True) 
nx.algorithms.degree_centrality(FG) 

# 图的平均边密度 
nx.density(FG)

# 0.09047619047619047

运行结果（对图进行可视化）

「求图中所有路径的平均最短路径长度」

#图中所有路径的平均最短路径长度
nx.average_shortest_path_length(FG) 

# 2.36984126984127

运行结果

「对于一个度为k的节点-求的邻居度的平均值」

#对于一个度为k的节点-它的邻居度的平均值是多少
nx.average_degree_connectivity(FG) # For a node of degree k - What is the average of its neighbours' degree?

#{20: 1.95, 1: 19.307692307692307, 2: 19.0625, 17: 2.0588235294117645, 3: 19.0}

运行结果

在这里插入图片描述

5、计算航线

# 找出所有 JAX 到 DFW 的航线
for path in nx.all_simple_paths(FG, source='JAX', target='DFW'):
    print(path)

#找出从JAX到DFW的dijkstra路径。
dijpath = nx.dijkstra_path(FG, source='JAX', target='DFW')
dijpath # ['JAX', 'JFK', 'SEA', 'EWR', 'DFW'] 下图中的最后一行

运行结果

「从所有航线中找出 飞行时间最短的路径」

# 从所有航线中找出 飞行时间最短的路径
shortpath = nx.dijkstra_path(FG, source='JAX', target='DFW', weight='air_time')
shortpath
# ['JAX', 'JFK', 'BOS', 'EWR', 'DFW']

运行结果：

注意事项

  • 起始点和目的地可以作为节点，其他信息应当作为节点或边属性；单条边可以被认为是一段旅程。这样的旅程将有不同的时间，航班号，飞机尾号等相关信息。
  • 注意到年，月，日和时间信息分散在许多列；想创建一 个包含所有这些信息的日期时间列，还需要将预计的 （scheduled）和实际的(actual)到达离开时间分开；最终 应该有4个日期时间列（预计到达时间、预计起飞时间、 实际到达时间和实际起飞时间）
  • 时间格式问题
  • 数据类型问题
  • NaN值的麻烦

结语

学习来源：B站及其课堂PPT，对其中代码进行了复现

?

参考：「链接」

PPT中错误有点多 用了挺久的时间学习原理找错误 哎～

以上代码均已运行成功！ 环境：Vs Code

?

「文章仅作为学习笔记，记录从0到1的一个过程」

希望对您有所帮助，如有错误欢迎小伙伴指正～

相关推荐

为何越来越多的编程语言使用JSON（为什么编程）

JSON是JavascriptObjectNotation的缩写，意思是Javascript对象表示法，是一种易于人类阅读和对编程友好的文本数据传递方法，是JavaScript语言规范定义的一个子...

何时在数据库中使用 JSON（数据库用json格式存储）

在本文中，您将了解何时应考虑将JSON数据类型添加到表中以及何时应避免使用它们。每天?分享?最新?软件?开发?，Devops，敏捷?，测试?以及?项目?管理?最新?，最热门?的?文章?，每天?花?...

MySQL 从零开始:05 数据类型（mysql数据类型有哪些,并举例）

前面的讲解中已经接触到了表的创建，表的创建是对字段的声明，比如：上述语句声明了字段的名称、类型、所占空间、默认值和是否可以为空等信息。其中的int、varchar、char和decimal都...

JSON对象花样进阶（json格式对象）

一、引言在现代Web开发中，JSON（JavaScriptObjectNotation）已经成为数据交换的标准格式。无论是从前端向后端发送数据，还是从后端接收数据，JSON都是不可或缺的一部分。...

深入理解 JSON 和 Form-data（json和formdata提交区别）

在讨论现代网络开发与API设计的语境下，理解客户端和服务器间如何有效且可靠地交换数据变得尤为关键。这里，特别值得关注的是两种主流数据格式：...

JSON 语法（json 语法 priority）

JSON语法是JavaScript语法的子集。JSON语法规则JSON语法是JavaScript对象表示法语法的子集。数据在名称/值对中数据由逗号分隔花括号保存对象方括号保存数组JS...

JSON语法详解（json的语法规则）

JSON语法规则JSON语法是JavaScript对象表示法语法的子集。数据在名称/值对中数据由逗号分隔大括号保存对象中括号保存数组注意：json的key是字符串,且必须是双引号，不能是单引号...

MySQL JSON数据类型操作（mysql的json）

概述mysql自5.7.8版本开始，就支持了json结构的数据存储和查询，这表明了mysql也在不断的学习和增加nosql数据库的有点。但mysql毕竟是关系型数据库，在处理json这种非结构化的数据...

JSON的数据模式（json数据格式示例）

像XML模式一样，JSON数据格式也有Schema，这是一个基于JSON格式的规范。JSON模式也以JSON格式编写。它用于验证JSON数据。JSON模式示例以下代码显示了基本的JSON模式。{"...

前端学习——JSON格式详解（后端json格式）

JSON(JavaScriptObjectNotation)是一种轻量级的数据交换格式。易于人阅读和编写。同时也易于机器解析和生成。它基于JavaScriptProgrammingLa...

什么是 JSON:详解 JSON 及其优势（什么叫json）

现在程序员还有谁不知道JSON吗？无论对于前端还是后端，JSON都是一种常见的数据格式。那么JSON到底是什么呢？JSON的定义...

PostgreSQL JSON 类型:处理结构化数据

PostgreSQL提供JSON类型，以存储结构化数据。JSON是一种开放的数据格式，可用于存储各种类型的值。什么是JSON类型？JSON类型表示JSON(JavaScriptO...

JavaScript:JSON、三种包装类（javascript 包）

JOSN:我们希望可以将一个对象在不同的语言中进行传递，以达到通信的目的，最佳方式就是将一个对象转换为字符串的形式JSON（JavaScriptObjectNotation）-JS的对象表示法...

Python数据分析 只要1分钟 教你玩转JSON 全程干货

Json简介：Json，全名JavaScriptObjectNotation,JSON(JavaScriptObjectNotation(记号、标记))是一种轻量级的数据交换格式。它基于J...

比较一下JSON与XML两种数据格式?（json和xml哪个好）

JSON（JavaScriptObjectNotation）和XML（eXtensibleMarkupLanguage）是在日常开发中比较常用的两种数据格式，它们主要的作用就是用来进行数据的传...

取消回复欢迎 你 发表评论:

请填写验证码
一周热门
最近发表
标签列表