鄰接矩陣知A怎么求A2 怎樣求鄰接矩陣？

對于一個無向圖生成的鄰接矩陣，已知第A行和第B行（A<B），求AB的最短路徑，如何用鄰接矩陣求出距離矩陣？怎么根據(jù)鄰接矩陣來求可達矩陣？對于ISM有些我不是很懂，能解決我疑問的追加50分？怎樣求鄰接矩陣？根據(jù)有向圖 求鄰接矩陣 可達性矩陣 區(qū)域分解 級間分解 縮減矩陣，鄰接矩陣的二次方怎么算？

本文導(dǎo)航

• 對于一個無向圖生成的鄰接矩陣，已知第A行和第B行（A<B），求AB的最短路徑
• 如何用鄰接矩陣求出距離矩陣？
• 怎么根據(jù)鄰接矩陣來求可達矩陣？對于ISM有些我不是很懂，能解決我疑問的追加50分。
• 怎樣求鄰接矩陣？
• 根據(jù)有向圖 求鄰接矩陣 可達性矩陣 區(qū)域分解 級間分解 縮減矩陣
• 鄰接矩陣的二次方怎么算

對于一個無向圖生成的鄰接矩陣，已知第A行和第B行（A<B），求AB的最短路徑

最短路徑算法的作用就是在圖中找出任意兩點間最短距離的途徑，比如可以在地圖上找出任兩個城市之間路程最短的那條路徑。

具體運用請見：

/Article/Exam/otherks/200509/1210.html

有兩種算法可以實現(xiàn)，一種是迪杰斯特拉（Dijkstra）算法，一種是弗洛伊德（Floyd）算法。

迪杰斯特拉（Dijkstra）算法：

（給出一個出發(fā)點，可算出該出發(fā)點到所有其它點的最短距離還有具體路徑）

算法過程：

一，用D[v]記錄任一點v到出發(fā)點的最短距離，建立一S集合且為空，用以記錄已找出最短距離的點。

二，掃描非S集中D[]值最小的節(jié)點D[w]，也就是找出下一條最短路徑，把節(jié)點w加入S集中。

三，更新所有非S集中的D[]值，看看是否可通過新加入的w點讓其距離更短：if(D[w]+ < D[v]) then D[v]=D[w]+;

四，跳轉(zhuǎn)到（二）操作，循環(huán)（頂點數(shù)－1）次，依次找出所有頂點的最短路徑。

算法理解：

先證明：下一條最短路徑一定是經(jīng)過S集中的頂點，或是直接到達出發(fā)點的。

也就是說下一條最短路徑一定不經(jīng)過S集外的頂點。

證明：如下圖，v為出發(fā)點，假使w為下一條最短路徑的頂點，則一定小于，否則稱k為下一條最短路徑，而不是w，所以 < 則 < 所以w一定通過S集中的頂點。

第一條最短路徑當(dāng)然是直到出發(fā)點且最短的那條，所以可以掃描初始化后的D[]直接找出最短那條，然后根據(jù)以上證明可得下一條最短路徑一定是通過剛找出的那條的，由于下一條最短路徑一定是通過S集的，所有不用每次都掃描所有的路徑，所以只用更新有通過剛加入的頂點的路徑D[]值（三操作）。再掃描出最短的D[]值，加入S集中（二操作），再更新所有D[]值，依次找出所有頂點。

弗洛伊德（Floyd）算法：

（算出所有每對頂點間的最短路徑）

算法過程：

一，用D[v][w]記錄每一對頂點的最短距離。

二，依次掃描每一個點，并以其為基點再遍歷所有每一對頂點D[][]的值，看看是否可用過該基點讓這對頂點間的距離更小。

算法理解：

最短距離有三種情況：

一，兩點的直達距離最短。（如下圖）

二，兩點間只通過一個中間點而距離最短。（圖）

三，兩點間用通過兩各以上的頂點而距離最短。（圖）

對于第一種情況：在初始化的時候就已經(jīng)找出來了且以后也不會更改到。

對于第二種情況：弗洛伊德算法的基本操作就是對于每一對頂點，遍歷所有其它頂點，看看可否通過這一個頂點讓這對頂點距離更短，也就是遍歷了圖中所有的三角形（算法中對同一個三角形掃描了九次，原則上只用掃描三次即可，但要加入判斷，效率更低）。

對于第三種情況：如下圖的五邊形，可先找一點（比如x，使=2），就變成了四邊形問題，再找一點（比如y,使=2），可變成三角形問題了（v,u,w），也就變成第二種情況了，由此對于n邊形也可以一步步轉(zhuǎn)化成四邊形三角形問題。（這里面不用擔(dān)心哪個點要先找哪個點要后找，因為找了任一個點都可以使其變成（n－1）邊形的問題）。

如何用鄰接矩陣求出距離矩陣？

可以用Floyd法.先在d(i,j)內(nèi)填入鄰接矩陣

枚舉i,j,k, d(i,j)=min{d(i,k)+d(k,j)}

最后得到的d就是距離矩陣

怎么根據(jù)鄰接矩陣來求可達矩陣？對于ISM有些我不是很懂，能解決我疑問的追加50分。

這個你可以畫個簡單圖看看, 寫出它的鄰接矩陣A, 計算A^2, 體會一下A與A相乘時, 其中的1和1相乘恰好就是 一結(jié)點到另一結(jié)點再到另一結(jié)點的路, 有路就是1, 否則是0.

在這不好說清楚, 還需自己揣摩

怎樣求鄰接矩陣？

設(shè) a-z為1-25

若 A、B合作 則 s[1][2]=1 s[2][1]=1;

否則 二者都為0

根據(jù)有向圖 求鄰接矩陣 可達性矩陣 區(qū)域分解 級間分解 縮減矩陣

由題知相鄰矩陣A為：

可達性矩陣：

A1=A+I=

A2=A1的平方=

A3=A1的三次方=

A4=A1的四次方=

因為A2不等于A3=A4，所以可達性矩陣為M=A3

對M進行分解得

由表知，一級元素為5

去掉一級元素，對剩余部分繼續(xù)分解有

由表知，二級元素為2，4，6，8

去掉二級元素，對剩余部分繼續(xù)分解有

由表知，三級元素為1，7，四級元素為3

所以系統(tǒng)的遞階結(jié)構(gòu)模型就有了，縮減矩陣很簡單就得到了

望采納~

鄰接矩陣的二次方怎么算

2次冪是 1 2 3 1

0 0 0 1

0 0 1 0

0 0 0 0

先畫出有向圖,再計算點到點長度為2的通路條數(shù),這就是他的2次冪.