wordpress 隱藏內(nèi)容seo信息查詢
文章目錄
- 前言
- 一、圖論
- 基本概念
- 示例
- 二、代碼實(shí)現(xiàn)----Matlab
- 三、代碼實(shí)現(xiàn)----python
- 總結(jié)
前言
通過模型算法,熟練對Matlab和python的應(yīng)用。
學(xué)習(xí)視頻鏈接:
https://www.bilibili.com/video/BV1EK41187QF?p=36&vd_source=67471d3a1b4f517b7a7964093e62f7e6
一、圖論
圖論(Graph Theory)是數(shù)學(xué)和計(jì)算機(jī)科學(xué)中的一個重要分支,專門研究圖(graphs)的性質(zhì)及其應(yīng)用。圖是一種抽象的數(shù)據(jù)結(jié)構(gòu),用于表示對象及其相互關(guān)系。
基本概念
-
圖(Graph):
一個圖由一組頂點(diǎn)(或稱為節(jié)點(diǎn))和一組邊(連接這些頂點(diǎn)的線)組成。形式上,一個圖 ( G ) 可以表示為 ( G = (V, E) ),其中 ( V ) 是頂點(diǎn)集合,( E ) 是邊集合。 -
頂點(diǎn)(Vertex):
圖中的一個基本單位,代表某個對象。頂點(diǎn)的集合通常用 ( V ) 表示。 -
邊(Edge):
頂點(diǎn)之間的連接。邊的集合通常用 ( E ) 表示。邊可以是有向的(directed)或無向的(undirected)。 -
有向圖(Directed Graph or Digraph):
邊有方向的圖,即邊表示從一個頂點(diǎn)指向另一個頂點(diǎn)的箭頭。 -
無向圖(Undirected Graph):
邊沒有方向的圖,即邊僅表示頂點(diǎn)之間的連接,沒有方向性。 -
權(quán)重(Weight):
在一些圖中,邊可以附帶一個數(shù)值,稱為權(quán)重(weight),表示頂點(diǎn)之間的距離、成本或其他度量。 -
路徑(Path):
從一個頂點(diǎn)到另一個頂點(diǎn)經(jīng)過的一系列邊和頂點(diǎn)。路徑的長度通常表示為路徑上所有邊的權(quán)重之和。
示例
- 求 0 到 8 的最短距離。
二、代碼實(shí)現(xiàn)----Matlab
在MATLAB中,shortestpath
函數(shù)用于計(jì)算圖中兩個節(jié)點(diǎn)之間的最短路徑。
shortestpath
函數(shù)的基本語法如下:
[P, d] = shortestpath(G, s, t)
G
:一個圖對象,通常使用graph
或digraph
函數(shù)創(chuàng)建。s
:起始節(jié)點(diǎn)。t
:目標(biāo)節(jié)點(diǎn)。P
:返回的最短路徑上的節(jié)點(diǎn)序列。d
:返回的最短路徑的長度(或權(quán)重和)。
% 定義圖的邊和權(quán)重
s = [9 9 1 1 3 3 3 2 2 5 5 7 7 8]; % 起始節(jié)點(diǎn)編號
t = [1 2 2 3 4 6 7 4 5 4 7 6 8 6]; % 終止節(jié)點(diǎn)編號
w = [4 8 3 8 2 7 4 1 6 6 2 14 10 9]; % 邊的權(quán)重% 創(chuàng)建一個圖形對象 G
G = graph(s,t,w);% 繪制圖形 G,并將邊的權(quán)重添加到圖形上
% G.Edges.Weight 表示圖形對象 G 中所有邊的權(quán)重值,'EdgeLabel' 表示在圖形上顯示這些權(quán)重值
plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2)
% 隱藏圖形的坐標(biāo)軸
set( gca, 'XTick', [], 'YTick', [] );% shortestpath 函數(shù)計(jì)算從節(jié)點(diǎn) 9 到節(jié)點(diǎn) 8 的最短路徑和路徑長度,并將路徑和路徑長度分別存儲在 P 和 d 中
[P,d] = shortestpath(G, 9, 8);
% 在圖形 G 中高亮顯示最短路徑
% highlight 函數(shù)高亮圖形對象 myplot 中的路徑 P,'EdgeColor', 'r' 表示將路徑顏色設(shè)置為紅色。
myplot = plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2);
highlight(myplot, P, 'EdgeColor', 'r')
運(yùn)行結(jié)果:
三、代碼實(shí)現(xiàn)----python
在 Python 中,可以使用 NetworkX
庫和 Matplotlib
庫來實(shí)現(xiàn)帶有權(quán)重的無向圖的創(chuàng)建和繪制。
import networkx as nx
import matplotlib.pyplot as plt# 定義圖的邊和權(quán)重
edges = [(9, 1, 4), (9, 2, 8), (1, 2, 3), (1, 3, 8), (3, 4, 2), (3, 6, 7), (3, 7, 4), (2, 4, 1), (2, 5, 6), (5, 4, 6), (5, 7, 2), (7, 6, 14), (7, 8, 10), (8, 6, 9)]# 創(chuàng)建一個有加權(quán)邊的圖形對象 G
G = nx.Graph()
G.add_weighted_edges_from(edges)# 計(jì)算從節(jié)點(diǎn) 9 到節(jié)點(diǎn) 8 的最短路徑和路徑長度
path = nx.shortest_path(G, source=9, target=8, weight='weight')
path_length = nx.shortest_path_length(G, source=9, target=8, weight='weight')# 繪制圖形 G,并將邊的權(quán)重添加到圖形上
pos = nx.spring_layout(G) # 計(jì)算節(jié)點(diǎn)位置
nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray', node_size=500, font_size=10, width=2)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)# 在圖形 G 中高亮顯示最短路徑
path_edges = list(zip(path, path[1:]))
nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='r', width=2)# 隱藏圖形的坐標(biāo)軸
plt.gca().set_xticks([])
plt.gca().set_yticks([])# 顯示結(jié)果
print('最短路徑:', path)
print('最短路徑長度:', path_length)plt.show()
運(yùn)行結(jié)果:
總結(jié)
本文介紹了使用圖論求最短路徑,并通過典型示例建立模型,分別使用Matlab和python進(jìn)行代碼編寫。