2016.6.30—matlab sparse生成稀疏矩阵并求最短路

matlab有很多自带的函数，可以实现很强大的功能。最近在做分析互联网拓扑的工作。目前互联网拓扑共有49451个AS。每个AS之间至少有4个链路。我所做的工作是分析AS之间的最短跳数。其实是很简单的工作。使用matlab两三个函数就可以搞定。问题在于如何把如此庞大的数据集输入进matlab。尝试了一下如果采用邻接矩阵的方式，5万个节点的邻接矩阵大小为4个G左右。电脑8G内存，根本无法导入。于是，需要采用稀疏矩阵的方式。那么什么是稀疏矩阵呢？稀疏矩阵是省略了矩阵的0元素后的矩阵，这样可以大大减少一个矩阵的存储空间。那么思路就是想办法吧邻接矩阵转化为稀疏矩阵。果然，转化完之后可以把内存大小从4G缩小到200M。多么犀利的一个比例。然后可以用的graphallshortestpaths去求最短路矩阵。注意转化稀疏矩阵的函数sparse的第四个第五个参数规定矩阵的行数和列数。因为graphallshortestpaths需要输入n*n的稀疏矩阵。而sparse有可能转化出一个n*m的矩阵。这一点需要注意。