average shortest path in unweighted undirected graph

Question

can somebody help me? I'm a bit lost. Well, i'm not an expert in Java for sure.

I need to write java code algorithm to calculate an average shortest path in unweighted undirected graph (network). This graph is a grid of 100 nodes (10 x 10) and would like to search all shortest paths between all pairs (nodes) in network and then divide by number of shortest paths to get an average shotrest path. Is this posible by modifying Dijstra's algorithm? Can someone show me how, please?

dijkstra's alghoritm

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];
    }
}

Teresa Carrigan Teresa Carrigan · Accepted Answer · 2014-02-01T20:55:55

Dijkstra's algorithm will give you the shortest path from a given node to all other nodes in the connected graph. One way to get your average is to iterate through each node of the graph, running Dijkstra's algorithm to get the shortest distance from that node to each of the others, and taking the average of paths starting from that node. Accumulate the "average of paths starting from current node" as you iterate. Divide by number of nodes when you finish iterating.

This is a brute force approach, and will calculate each distance twice, but it should give you the correct average.

average shortest path in unweighted undirected graph

1 Answers