
* 用来计算介数
* 要计算所有的最短路径,用DIJ计算最短路径的时候我们可以发现一个规律:最后生成的结果是最小生成树,而一棵树是可以用一个一维数组表示的。
* 所以本代码在计算介数的时候具有和DIJ相同的时间复杂度。
*/
public class Betweeness {
private double[][] dis
private int N
Betweeness(double[][] dis)
{
this.dis = dis
this.N = dis.length
}
/**
* @return
*/
public double[] getBetweeness()
{
double[] b = new double[N]
for(int start = 0 start < N start++)
{
int[] path = getPath(start) // 保存树的结构
int[] num = new int[N] // 一个节点的路径的数目
int[] used = new int[N] // 0:初始-->1:有子节点 0--->2:把没有子节点的处理粗拿棚
// 每次处理的时候找到没有子节点的点,然后将它的个数加到它的父节点中
for(int i = 0 i < N i++)
{
for(int j = 0 j < N j++)
{
if(path[j] != -1 && used[path[j]] == 0)
{
used[path[j]] = 1
}
}
for(int j = 0 j < N j++)
{
if(used[j] == 0 && path[j] >= 0)
{
num[path[j]] += 1 + num[j]
used[j] = 2
}
}
for(int j = 0 j < N j++)
{
if(used[j] == 1)
岩则 {
used[j] = 0
}
}
}
for(int i = 0 i < N i++)
{
b[i] += num[i]
}
}
double sum = N*N - N
for(int i = 0 i < N i++)
{
b[i] /= sum
}
return b
}
/**
* 计算从start出发到各个节点的最短路敏物径,返回这棵最小生成树
* @param start
* @return
*/
public int[] getPath(int start)
{
int[] path = new int[N]
boolean[] used = new boolean[N]
double[] minDis = new double[N]
for(int i = 0 i < N i++)
{
path[i] = -1
minDis[i] = -1.0
}
used[start] = true
minDis[start] = 0.0
for(int i = 1 i < N i++)
{
for(int j = 0 j < N j++)
{
if(used[j] == true || dis[start][j] < 0){
continue
}
if(dis[start][j] >= 0.0 && (minDis[j] < 0.0 || minDis[j] > minDis[start] + dis[start][j]))
{
path[j] = start
minDis[j] = minDis[start] + dis[start][j]
}
}
start = -1
for(int j = 0 j < N j++)
{
if(minDis[j] < 0.0 || used[j] == true)
{
continue
}
if(start == -1 || minDis[start] > minDis[j])
{
start = j
used[start] = true
}
}
if(start == -1)
{
break
}
}
return path
}
/////////////////////////////////////////////////////////////////////
public static void main(String[] main){
double[][] dis = {{0, 1, 5, 2},
{1, 0, 4, 6},
{5, 4, 0, 3},
{2, 6, 3, 0}}
double[] b = new Betweeness(dis).getBetweeness()
for(int i = 0 i < b.length i++)
{
System.out.println(b[i])
}
}
}
介数(Betweenness)由Freeman于1979首先提图 设σst=σts代表节点s∈V结点 t∈V路径数目设σst(v)代表节御羡点s结让笑点t短路径经节点v∈V数目则节点介数定义:我同定义边介数图 设σst(e)代表节点s节点t短路镇滑拍径经边e∈E 数目边e两端点别u、v则边介数定义:
节点v度指与节点邻接节点数记做deg(v)其图G度δ(G),度记做Δ(G).
公式都打 我发油箱.
欢迎分享,转载请注明来源:内存溢出
微信扫一扫
支付宝扫一扫
评论列表(0条)