本期我們進(jìn)行運(yùn)籌學(xué)之圖與網(wǎng)絡(luò)分析算法的講解，我們將對圖與網(wǎng)絡(luò)分析的基礎(chǔ)知識進(jìn)行一個簡單的回顧，并介紹求解最短路問題的MATLAB和Python相關(guān)代碼，以幫助大家利用工具快速求解最短路問題，做到事半功倍。由于篇幅有限，小編接下來只展示部分代碼，小伙伴們可以關(guān)注“運(yùn)籌說”公眾號→后臺回復(fù)“算法介紹之圖與網(wǎng)絡(luò)分析（一）”獲取完整代碼。話不多說，我們一起來看看吧！

一、基礎(chǔ)知識

1、圖

★ 基本概念

(1)圖：一個圖是由點(diǎn)集V={vi}和V中元素的無序?qū)Φ囊粋€集合E={ek}所構(gòu)成的二元組，記為G=(V,E)，V中的元素vi叫做頂點(diǎn)，E中的元素ek叫做邊。

(2)子圖：圖G=(V,E)，若E'是E的子集，V'是V的子集，且E'中的邊僅與V'中的頂點(diǎn)相關(guān)聯(lián)，則稱G'=(V',E')是G的一個子圖。特別是，若V'=V，則G'稱為G的生成子圖(支撐子圖)。? ? ? ? ? ? ? ??

(3)鏈：在無向圖G=(V,E)中，由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為鏈。

(4)連通圖：一個圖中任意兩點(diǎn)間至少有一條鏈相連，則稱此圖為連通圖。

(5)權(quán)：與點(diǎn)或邊有關(guān)的某些數(shù)量指標(biāo)，權(quán)可以代表如距離、費(fèi)用、通過能力（容量）等。

(6)網(wǎng)絡(luò)（賦權(quán)圖）：點(diǎn)或邊帶有某種數(shù)量指標(biāo)（時間、費(fèi)用、距離等）的圖，稱為網(wǎng)絡(luò)（賦權(quán)圖）。

★ 圖的分類

(1)有向圖與無向圖

有向圖：如果邊(vi ,vj)的端點(diǎn)有序，即它表示以vi為始點(diǎn)，vj為終點(diǎn)的有向邊（或稱?。?，這時圖G稱為有向圖。

無向圖：對于任一條邊(vi ,vj)屬于E，如果邊(vi ,vj)端點(diǎn)無序，則它是無向邊，此時圖G稱為無向圖。

(2)簡單圖與多重圖

簡單圖：不含環(huán)和多重邊的圖稱為簡單圖。

多重圖：含有多重邊的圖稱為多重圖。

2、樹

★ 基本性質(zhì)

(1)連通且不含圈的無向圖稱為樹。

(2)任何樹至少有兩個懸掛節(jié)點(diǎn)。

(3)如果樹的節(jié)點(diǎn)個數(shù)為m，則邊的個數(shù)為m-1。

(4)樹中任意兩個節(jié)點(diǎn)之間只有唯一的一條鏈。

(5)在樹的任意兩個不相鄰的節(jié)點(diǎn)之間增加一條邊，則形成唯一的圈。

(6)從樹中任意去掉一條邊，則余下的圖是不連通的。

(7)由圖的所有節(jié)點(diǎn)（m個）和圖的m-1條邊組成的樹稱為圖的支撐樹。

★ 最小生成樹

(1)定義

一棵生成樹所有樹枝上權(quán)的總和，稱為這個生成樹的權(quán)。具有最小權(quán)的生成樹稱為最小生成樹（最小支撐樹），簡稱最小樹。

(2) 求解方法

3、最短路問題

★ 問題描述

最短路問題的一般提法如下：

設(shè)G=(V,E)為連通圖，圖中各邊(vi ,vj)有權(quán)l(xiāng)ij (lij=∞表示vi ,vj間無邊)，vs ，vt為圖中任意兩點(diǎn)，求一條道路m，使它是從vs 到vt的所有路中總權(quán)最小的道路。即：

★ Dijkstra算法

可用于求解指定兩點(diǎn)vs, vt間的最短路，或從指定點(diǎn)vs到其余各點(diǎn)的最短路，目前被認(rèn)為是求無負(fù)權(quán)網(wǎng)絡(luò)最短路的最好方法。

算法的基本思路：若序列{vs,v1,…, vn-1, vn}是從vs到vn的最短路，則序列{vs,v1,…, vn-1}必為從vs到 vn-1的最短路。

★ Floyd算法

Floyd算法又稱為插點(diǎn)法，是一種用于求出網(wǎng)絡(luò)上任意兩點(diǎn)間最短路徑的算法，邊權(quán)可正可負(fù)。

為計算方便，令網(wǎng)絡(luò)的權(quán)矩陣為D=(dij)n×n，有

此時算法基本步驟：

(1)輸入權(quán)矩陣D(0)=D。

(2)依次計算D(k) =(dij (k))n×n , k=1,2,3,...,n，其中

(3)D(n) =(dij (n))n×n 中元素dij (n)就是vi到vj的最短路長。

★ 算法總結(jié)

二、算法實(shí)現(xiàn)

1、Dijkstra算法

（1）例題介紹

用Dijkstra算法求下圖中v1點(diǎn)到v6點(diǎn)的最短路。

（2）平臺實(shí)現(xiàn)

我們以上述例題為例，借助MATLAB和Python介紹實(shí)現(xiàn)Dijkstra算法的相關(guān)代碼。

①M(fèi)ATLAB

★ 代碼展示

★ 代碼調(diào)用

代碼運(yùn)行及最終結(jié)果展示如下，可以看到用Dijkstra算法求得v1到v6的最短路為13，具體路線為：v1→v2→v5→v6。

②Python

★ 代碼展示

★ 代碼調(diào)用

代碼運(yùn)行及最終結(jié)果展示如下，可以看到用Dijkstra算法求得v1到v6的最短路為13，本例中Python代碼以0代表起點(diǎn)v1，以5代表終點(diǎn)v6，最終結(jié)果由終點(diǎn)指向起點(diǎn)：5→4→1→0，對應(yīng)到例題中起點(diǎn)到終點(diǎn)最短路徑的具體路線為：v1→v2→v5→v6。

2、Floyd算法

（1）例題介紹

用Floyd算法求下圖中任意兩點(diǎn)間的最短路。

（2）平臺實(shí)現(xiàn)

我們以上述例題為例，借助MATLAB和Python介紹實(shí)現(xiàn)求解Floyd算法的相關(guān)代碼。

①M(fèi)ATLAB

★ 代碼展示

★ 代碼調(diào)用

②Python

★ 代碼展示

★ 代碼調(diào)用

（3）結(jié)果展示

用MATLAB和Python運(yùn)行求解Floyd算法的程序，各點(diǎn)之間的最短距離如下表所示：

三、參考資料

【Dijkstra算法MATLAB實(shí)現(xiàn)】

https://blog.csdn.net/weixin_41971010/article/details/107666810

【Dijkstra算法Python實(shí)現(xiàn)】

https://blog.csdn.net/weixin_42875283/article/details/124341524

【Floyd算法MATLAB實(shí)現(xiàn)】

https://blog.csdn.net/qq_61123461/article/details/120047942

【Floyd算法Python實(shí)現(xiàn)】

https://blog.csdn.net/AivenZhong/article/details/93770197

本期的內(nèi)容就介紹到這里，想要進(jìn)一步了解運(yùn)籌學(xué)，關(guān)注本公眾號，快快學(xué)起來吧！

作者 | 尹萌娟 王連聚

責(zé)編 | 劉文志

審核 | 徐小峰