邻接矩阵知A怎么求A2 怎样求邻接矩阵？

绝恋红茶2022-08-11 18:04:472148

对于一个无向图生成的邻接矩阵，已知第A行和第B行（A<B），求AB的最短路径，如何用邻接矩阵求出距离矩阵？怎么根据邻接矩阵来求可达矩阵？对于ISM有些我不是很懂，能解决我疑问的追加50分？怎样求邻接矩阵？根据有向图求邻接矩阵可达性矩阵区域分解级间分解缩减矩阵，邻接矩阵的二次方怎么算？

本文导航

对于一个无向图生成的邻接矩阵，已知第A行和第B行（A<B），求AB的最短路径
如何用邻接矩阵求出距离矩阵？
怎么根据邻接矩阵来求可达矩阵？对于ISM有些我不是很懂，能解决我疑问的追加50分。
怎样求邻接矩阵？
根据有向图求邻接矩阵可达性矩阵区域分解级间分解缩减矩阵
邻接矩阵的二次方怎么算

对于一个无向图生成的邻接矩阵，已知第A行和第B行（A<B），求AB的最短路径

最短路径算法的作用就是在图中找出任意两点间最短距离的途径，比如可以在地图上找出任两个城市之间路程最短的那条路径。

具体运用请见：

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

有两种算法可以实现，一种是迪杰斯特拉（Dijkstra）算法，一种是弗洛伊德（Floyd）算法。

迪杰斯特拉（Dijkstra）算法：

（给出一个出发点，可算出该出发点到所有其它点的最短距离还有具体路径）

算法过程：

一，用D[v]记录任一点v到出发点的最短距离，建立一S集合且为空，用以记录已找出最短距离的点。

二，扫描非S集中D[]值最小的节点D[w]，也就是找出下一条最短路径，把节点w加入S集中。

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

四，跳转到（二）操作，循环（顶点数－1）次，依次找出所有顶点的最短路径。

算法理解：

先证明：下一条最短路径一定是经过S集中的顶点，或是直接到达出发点的。

也就是说下一条最短路径一定不经过S集外的顶点。

证明：如下图，v为出发点，假使w为下一条最短路径的顶点，则一定小于，否则称k为下一条最短路径，而不是w，所以 < 则 < 所以w一定通过S集中的顶点。

第一条最短路径当然是直到出发点且最短的那条，所以可以扫描初始化后的D[]直接找出最短那条，然后根据以上证明可得下一条最短路径一定是通过刚找出的那条的，由于下一条最短路径一定是通过S集的，所有不用每次都扫描所有的路径，所以只用更新有通过刚加入的顶点的路径D[]值（三操作）。再扫描出最短的D[]值，加入S集中（二操作），再更新所有D[]值，依次找出所有顶点。

弗洛伊德（Floyd）算法：

（算出所有每对顶点间的最短路径）

算法过程：

一，用D[v][w]记录每一对顶点的最短距离。

二，依次扫描每一个点，并以其为基点再遍历所有每一对顶点D[][]的值，看看是否可用过该基点让这对顶点间的距离更小。

算法理解：

最短距离有三种情况：

一，两点的直达距离最短。（如下图）

二，两点间只通过一个中间点而距离最短。（图）

三，两点间用通过两各以上的顶点而距离最短。（图）

对于第一种情况：在初始化的时候就已经找出来了且以后也不会更改到。

对于第二种情况：弗洛伊德算法的基本操作就是对于每一对顶点，遍历所有其它顶点，看看可否通过这一个顶点让这对顶点距离更短，也就是遍历了图中所有的三角形（算法中对同一个三角形扫描了九次，原则上只用扫描三次即可，但要加入判断，效率更低）。

对于第三种情况：如下图的五边形，可先找一点（比如x，使=2），就变成了四边形问题，再找一点（比如y,使=2），可变成三角形问题了（v,u,w），也就变成第二种情况了，由此对于n边形也可以一步步转化成四边形三角形问题。（这里面不用担心哪个点要先找哪个点要后找，因为找了任一个点都可以使其变成（n－1）边形的问题）。