CareerCup

If it's a connected and directed graph a possible solution could be:

1. Find all distances between each node of the graph, Djikstra applied for each node or else Floyd-Warshall algorithm could be used.

2. iterate over each node of graph and calculate average distance by summing all distances of node from all others and dividing it by N (size of graph).

3. Keep track of the min in the 2nd step and return min.

A sample implementation in Java using Floyd-warshall (Djikstra would be eventually better for performance for the sake of simplicity I'm using floyd-warshall in this example since the code is simpler):

class AllPairShortestPath
{
	final static int INF = 99999, V = 4;

	void minAverageDist(int graph[][])
	{
		int dist[][] = new int[V][V];
		float averageDist[] = new float[V];
		int i, j, k;

// step 1 - Floyd warshall - find all shortest distances between nodes
		for (i = 0; i < V; i++)
			for (j = 0; j < V; j++)
				dist[i][j] = graph[i][j];

		for (k = 0; k < V; k++)
		{
			// Pick all vertices as source one by one
			for (i = 0; i < V; i++)
			{
				// Pick all vertices as destination for the
				// above picked source
				for (j = 0; j < V; j++)
				{
					// If vertex k is on the shortest path from
					// i to j, then update the value of dist[i][j]
					if (dist[i][k] + dist[k][j] < dist[i][j])
						dist[i][j] = dist[i][k] + dist[k][j];
				}
			}
		}
		
		// 2. once all distances are calculated for each node calculate average distance
		float min = INF;
		int minNode = 0;
		for (i = 0; i < V; i++) {
		    int sum = 0;
			for (j = 0; j < V; j++) {
			    sum += dist[i][j];
			}
			
			averageDist[i] = (float)sum / V;
			if (min > averageDist[i]) {
			    min = averageDist[i];
			    minNode = i;
			}
		}

		System.out.print("MIN dist average = " + min + " NODE = " + minNode);
	}

	public static void main (String[] args)
	{
		/* Let us create the following weighted graph
		10
		(0)------->(3)
		|		 /|\
		5 |		 |
		|		 | 1
		\|/		 |
		(1)------->(2)
		3		 */
		int graph[][] = { {0, 5, INF, 10},
						{INF, 0, 3, INF},
						{INF, INF, 0, 1},
						{INF, INF, INF, 0}
						};
		AllPairShortestPath a = new AllPairShortestPath();
		a.minAverageDist(graph);
	}
}