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

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

本文導(dǎo)航

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

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

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

具體運(yùn)用請(qǐng)見：

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

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

迪杰斯特拉（Dijkstra）算法：

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

算法過程：

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

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

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

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

算法理解：

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

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

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

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

弗洛伊德（Floyd）算法：

（算出所有每對(duì)頂點(diǎn)間的最短路徑）

算法過程：

一，用D[v][w]記錄每一對(duì)頂點(diǎn)的最短距離。

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

算法理解：

最短距離有三種情況：

一，兩點(diǎn)的直達(dá)距離最短。（如下圖）

二，兩點(diǎn)間只通過一個(gè)中間點(diǎn)而距離最短。（圖）

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

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

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

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

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

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

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

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

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

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

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

怎樣求鄰接矩陣？

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

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

否則 二者都為0

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

由題知相鄰矩陣A為：

可達(dá)性矩陣：

A1=A+I=

A2=A1的平方=

A3=A1的三次方=

A4=A1的四次方=

因?yàn)锳2不等于A3=A4，所以可達(dá)性矩陣為M=A3

對(duì)M進(jìn)行分解得

由表知，一級(jí)元素為5

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

由表知，二級(jí)元素為2，4，6，8

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

由表知，三級(jí)元素為1，7，四級(jí)元素為3

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

望采納~

鄰接矩陣的二次方怎么算

2次冪是 1 2 3 1

0 0 0 1

0 0 1 0

0 0 0 0

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