平均路劲程度和直径
1.平均路劲长度
平均路劲长度:任意两个节点之间的距离(节点i和j之间的距离定义为连接这两个节点最短路劲的边的数目)的平均值
当网络不联通的时候,平均距离将变得非常大,因此采用网络效率:
当i与j不联通的时候,1/d(ij)为0
小世界效应:网络规模很大但是平均距离却很小的性质称为小世界效应
网络直径:任意两个节点之间距离的最大值
网络中距离d定义为:联通节点对的数量占整个网络的中的联通的节点对的数量的比例;
网络的有效直径:整数d满足g(d-1) < 0.9, g(d) >=0.9,则d为网络的有效直径
最短路劲算法(Dijkstra):
1.存储边的关系
我们还需要用一个一维数组 dis 来存储 1 号顶点到其余各个顶点的初始路程: