目錄

• 圖的簡介
• 無向圖（Graph）
• • 生成帶權鄰接矩陣
  • 求兩點最短路徑
• 有向圖（Digraph）
• • 生成帶權鄰接矩陣
  • 求最短路徑

圖的簡介

圖是拓撲學中的一個重要概念，分為無向圖和有向圖兩種。圖有兩個重要屬性，即點（Node）和邊（Edge）。在圖的概念中，我們只關心點和邊的連接關系而并不關系他們在圖中的相對位置。
由點和邊連接的圖中，將邊賦予一定的權重，就可以將圖轉換為各種問題，例如TSP（旅行商）問題、（Shortest Path）最短路徑問題。本文先介紹如何借助圖以及賦予的邊的權值生成帶權鄰接矩陣，再介紹利用圖求兩點之間最短路徑的求法。

無向圖（Graph）

生成帶權鄰接矩陣

先介紹根據以下無向圖生成帶權鄰接矩陣的方法：

假設我們已經知道了每條邊的權重（紅色標定），該圖中有11個點，如果挨個寫出需要121個元素，對于此圖已經非常繁瑣。因此我給大家提供一種簡單的方法，只需要寫出圖中標定權值的邊即可達到目的。書寫規則如下：
A→A：標定權值是0
若A→B沒有路徑可以到達，標定權值為0
若A→C有路徑可以到達，根據建模需要標定權值
這樣，我們在手動書寫時，僅需要寫出非0邊的權重即可，每條邊只需要書寫一次，書寫方式如下：

W=zeros(11); W(1,2)=2; W(1,4)=1; W(1,3)=8; W(2,3)=6; W(2,5)=1; W(3,4)=7; W(3,5)=5; W(3,6)=1; W(3,7)=2; W(4,7)=9; W(5,6)=3; W(5,8)=2; W(5,9)=9; W(6,7)=4; W(6,9)=6; W(7,9)=3; W(7,10)=1; W(8,9)=7; W(8,11)=8; W(9,10)=1; W(9,11)=2; W(10,11)=4;

由于本例中為無向圖，因此生成的矩陣總滿足W(i,j)=W(j,i)，所以利用以下代碼書寫另一半：

n=size(W,1); for i=1:nfor j=i:nW(j,i)=W(i,j);%次對角線分隔的下三角部分根據上三角部分對稱end end G=graph(W,'upper');%根據帶權鄰接矩陣生成無向圖 plot(G,'EdgeLabel',G.Edges.Weight) title('標定權重的無向圖')

自動繪圖效果如下：

帶權鄰接矩陣W如下：

（如果要將平時我們認為的不能到達的路徑之間權重設定為Inf也很容易，不過在Matlab內置的函數shortestpath中，認為權重0即不設路徑）

求兩點最短路徑

格式：[path,distance]=shortestpath(G,1,6)
path返回的是路徑經過的點，distance是該路徑的長度

例如在工作區輸入：

>>[path,distance]=shortestpath(G,1,6)

顯示如下：

對照我們繪制的無向圖也很容易手動驗證，最短路徑即1→2→5→6，最短路徑的距離=2+1+3=6。

有向圖（Digraph）

生成帶權鄰接矩陣

有向圖示例如下：

創建一個數組，每一列依次保存起始點，出發點，以及帶權。按照和無向圖同樣的方法對每條邊書寫帶權：

W=[1 2 10;1 4 10;1 8 1;2 3 10;2 7 1;3 4 10;3 6 1;4 5 1;5 6 12;5 8 12;6 7 12;7 8 12;];

用類似的方法生成有向圖如下：

startpoints=W(:,1);%起始點集合 endpoints=W(:,2);%結束點集合 weights=W(:,3);%對應起始點和結束點的邊權重 G=digraph(startpoints,endpoints,weights);%生成有向圖 plot(G,'EdgeLabel',weights,'layout','force','Edgecolor','red')%畫出有向圖

效果如下：

求最短路徑

在工作區求取最短路徑格式如下：

格式：>> [path,distance]=shortestpath(G,s,t)

得到的結果如下：

在此需要說明的和無向圖的區別是，在這里我們只有起始點的點數比終點點數小才有路徑，否則沒有，因此如果按照如下條件調用，則會得到空集，利用這一個特點可以在程序中增加條件加以排除。
（if distance==Inf 或 if path==[]）

>> [path,distance]=shortestpath(G,8,2)

希望本文對您有幫助，謝謝閱讀

總結

以上是生活随笔為你收集整理的【Matlab】根据图生成带权邻接矩阵，并求出最短路径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。