文件名称：图论算法matlab c++
文件大小：19KB
文件格式：DOCX
更新时间：2021-08-16 14:53:57
c++ 图论 matlab
弗洛伊德算法， matlab有一个自带的biography类型，可以直接画图，自带图论各种算法，用起来相当舒服，我是个懒人，虽然学了三四遍图论的各种东西，或者没学会，或者没敲过代码，这次我依然不打算手撸一遍，既然有系统自带的，那就用自带的好了，怕记不住，自己做个笔记写在这里。 首先写一下matlab里如何表示一个图，一般用稀疏矩阵。matlab函数sparse用来生成稀疏矩阵。通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入两个矩阵，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P中的元素b[i][j]，表示顶点i到顶点j经过了b[i][j]记录的值所表示的顶点。 假设图G中顶点个数为N，则需要对矩阵D和矩阵P进行N次更新。初始时，矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞，矩阵P的值为顶点b[i][j]的j的值。 接下来开始，对矩阵D进行N次更新。第1次更新时，如果”a[i][j]的距离” > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表示”i与j之间经过第1个顶点的距离”)，则更新a[i][j]为”a[i][0]+a[0][j]”,更新b[i][j]=b[i][0]。 同理，第k次更新时，如果”a[i][j]的距离” > “a[i][k-1]+a[k-1][j]”，则更新a[i][j]为”a[i][k-1]+a[k-1][j]”,b[i][j]=b[i][k-1]。更新N次之后，操作完成移植入c++