如果有一个图有N个节点，并且我只得到每个节点到另一个节点的距离的N*N矩阵(对角线当然是0(，那么生成一个边尽可能少的图的最有效方法是什么？
对于n=4和矩阵
0 1 2 3
1 0 3 4
2 3 0 5
3 4 5 0
仅具有3个边就足够了，所有边都连接到第一节点。
- 来自1和2的边的长度为1
- 1和3的边的长度为2
- 从1到4的边的长度为3
"从每个节点到另一个节点的距离的N*N矩阵(对角线当然是0("；
这被称为邻接矩阵。它完全指定了图形。每个非sero值定义两个顶点之间的边。如果不更改图形，就无法将边的数量减少到非零值的数量以下。
只需使用矩阵作为关联矩阵创建一个完整的图，然后删除不需要的边。
当且仅当存在与(a,b)相同长度的从a到b的另一路径时，边缘(a,b)是不需要的。也就是说，如果存在与a和b都不同的顶点c，使得
distance(a,b) = distance(a,c) + distance(c,b)
如果一些不在对角线上的距离为零或为负，则这将不起作用。