java - 未加权无向图中的平均最短路径

Question

有人可以帮助我吗？我有点失落。嗯，我肯定不是 Java 专家。

我需要编写java代码算法来计算未加权无向图(网络)中的平均最短路径。该图是一个由 100 个节点 (10 x 10) 组成的网格，希望搜索网络中所有对(节点)之间的所有最短路径，然后除以最短路径的数量以获得平均 Shotrest 路径。通过修改 Dijstra 算法可以实现吗？有人可以告诉我怎么做吗？

迪杰斯特拉算法

public static void dijkstra(int s, int[][] A, int N, int[] d) {
    int mini;  int[] visit = new int[N];
    for (int i=0;i<N;i++) {
        d[i] = N*N;    
        visit[i] = 0;  
    }
    d[s] = 0;           
    for (int k=0;k<N;k++) {
        mini = -1;
        for (int i=0;i<N;i++)
            if ((visit[i]==0) && ((mini == -1) || (d[i] < d[mini])))
                mini = i;
        visit[mini] = 1;
        for (int i=0;i<N;i++)
            if (A[mini][i]==1)
                if (d[mini] + A[mini][i] < d[i]) 
                    d[i] = d[mini] + A[mini][i];
    }
}

Answer 1

Dijkstra 算法将为您提供从给定节点到连接图中所有其他节点的最短路径。获得平均值的一种方法是迭代图表的每个节点，运行 Dijkstra 算法以获得从该节点到其他每个节点的最短距离，并取从该节点开始的路径的平均值。迭代时累积“从当前节点开始的路径的平均值”。完成迭代后除以节点数。

这是一种蛮力方法，会计算每个距离两次，但它应该会给出正确的平均值。