graphshortestpath 函數(shù)是用來(lái)解決最短路徑問(wèn)題的。

語(yǔ)法為：

　　[dist, path, pred]=graphshortestpath(G,S)
　　[dist, path, pred]=graphshortestpath(G,S,T)

　　G是稀疏矩陣，S是起點(diǎn)，T是終點(diǎn)。dist表示最短距離，path表示最短距離經(jīng)過(guò)的路徑節(jié)點(diǎn)，pred表示從S到每個(gè)節(jié)點(diǎn)的最短路徑中，目標(biāo)節(jié)點(diǎn)的先驅(qū)，即目標(biāo)節(jié)點(diǎn)的前面一個(gè)節(jié)點(diǎn)。比如一共有6個(gè)點(diǎn)，S=1，那么運(yùn)行這個(gè)函數(shù)后pred存的就是S=1這個(gè)節(jié)點(diǎn)到其它節(jié)點(diǎn)T'最短路徑上T'的前一個(gè)節(jié)點(diǎn)。這個(gè)函數(shù)也就是求出圖G上S到T的[dist,?path,?pred]，當(dāng)不寫(xiě)T時(shí)表示求S到其它所有點(diǎn)的[dist,?path,?pred]。

　　G是個(gè)稀疏矩陣，我的理解是稀疏矩陣就是含有大量0的矩陣，可能為了便于存儲(chǔ)和加快計(jì)算，才采用這種矩陣。G并不是圖的路徑權(quán)值矩陣，它由s[]向量和t[]向量和路徑權(quán)值向量w[]構(gòu)成：G=spares(s,t,w)。也就是說(shuō)G應(yīng)該是個(gè)N*3的矩陣，第一行表示節(jié)點(diǎn)起點(diǎn)，第二行表示節(jié)點(diǎn)終點(diǎn)，第三行是權(quán)值。而且同一條無(wú)向邊不用重復(fù)寫(xiě)，因?yàn)橄冗@樣構(gòu)造的是個(gè)有向圖。無(wú)向圖需要這樣操作：UG=tril(G+G');就是把G和自己的轉(zhuǎn)置G'加起來(lái)再求下三角矩陣。

　　對(duì)于無(wú)向圖、有向圖搞明白了其它的就是一些參數(shù)、屬性的調(diào)整了。

　　附上文檔中的代碼，有改動(dòng)：

?

clc; W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21]; DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W); h=view(biograph(DG,[],'ShowWeights','on')) [dist,path,pred]=graphshortestpath(DG,1,6,'Directed','true') set(h.Nodes(path),'Color',[1 0.4 0.4]) edges=getedgesbynodeid(h,get(h.Nodes(path),'ID'));%我覺(jué)得這里就是獲得最短路徑的邊和ID set(edges,'LineColor',[1 0 0]) set(edges,'LineWidth',1.5) UG=tril(DG+DG'); bg=biograph(UG,[],'ShowArrows','off','ShowWeights','on'); h=view(bg) set(bg.nodes,'shape','circle'); [dist,path,pred]=graphshortestpath(UG,1,6,'Directed','false') set(h.Nodes(path),'Color',[1 0.4 0.4]) fowEdges=getedgesbynodeid(h,get(h.Nodes(path),'ID')); revEdges=getedgesbynodeid(h,get(h.Nodes(fliplr(path)),'ID'));%這里fliplr是反轉(zhuǎn)操作，比如把[1 2 3]變成[3 2 1]。由于是無(wú)向圖，所以正反都要求。 edges=[fowEdges;revEdges]; set(edges,'LineColor',[0.6 0.4 0.1]) set(edges,'LineWidth',1.5)

?

　　

?

　　

?

而對(duì)于graphallshortestpaths函數(shù)則是求所有點(diǎn)之間的最短距離：[dist] = graphallshortestpaths(G)

道理和上面那個(gè)函數(shù)很相似，當(dāng)然內(nèi)部實(shí)現(xiàn)的算法是不一樣的。

這還是文檔里的例程：

W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21]; DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W); view(biograph(DG,[],'ShowWeights','on')) graphallshortestpaths(DG) UG = tril(DG + DG') view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'))

　　

轉(zhuǎn)載于:https://www.cnblogs.com/zxhyxiao/p/9338481.html

總結(jié)

以上是生活随笔為你收集整理的【7.19 graphshortestpath graphallshortestpaths函数】matlab 求最短路径函数总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。