uva: 821 – Page Hopping ( Floyd Warshall )

821 – Page Hopping  ( Floyd Warshall )

Problem Analysis:

  • It was recently reported that, on the average, only 19 clicks are necessary to move from any page on the World Wide Web to any other page. That is, if the pages on the web are viewed as nodes in a graph, then the average path length between arbitrary pairs of nodes in the graph is 19
  • determine the average shortest path length between every pair of nodes, accurate to three fractional digits

Solution:

  •  this is a problem of finding all pairs shortest path in given graph ( pages/nodes/vertexes )
  • it can be solved using all pairs shortest paths Floyd Warshall algorithm

 

Java solution:

<pre>
import java.util.Scanner;

class Main_PageHopping_821 {

	public static void main(String[] args) {
		final int NoPath = 65000, limit=101;
		int node1, node2, testCase=0;
		int length[][];

		Scanner sc = new Scanner(System.in);

		while(true)
		{
			//if last test case exit
			node1 = sc.nextInt();
			node2 = sc.nextInt();

			if(node1==0 && node2 ==0) 	break;

			//init variables
			testCase++;
			length= new int[limit][limit];

			for(int i=0;i
				for(int j=0;j<limit;j++)
					length[i][j] = NoPath;

			//read inputs
			do
			{
				length[node1][node2] = 1;
				length[node1][node1] = length[node2][node2] = 0;

				node1 = sc.nextInt();
				node2 = sc.nextInt();

			}while(node1>0 && node2>0);

			//Floyd Warshall algorithm

			for(int k=1; k<limit; k++)
				for(int i=1; i < limit; i++)
					for(int j=1; j<limit; j++)
					{
						if(j==i) continue;

						if(length[i][j] > length[i][k] + length[k][j])
						{
							length[i][j] = length[i][k] + length[k][j];
						}
					}

			int nodes=0;
			float sum=0;

			for(int i=1; i < limit; i++)
			{
				for(int j=1;j<limit;j++)
				{
					if( i==j && length[i][i] == 0) nodes++;
					else if(i!=j && length[i][j] != NoPath)
					{
						sum+=length[i][j];
					}
					//System.out.print(length[i][j]+"  ");
				}
				//System.out.println("\n");
			}

			float pairs = nodes * (nodes - 1);
			//System.out.println(sum + "/" + pairs);
		System.out.format("Case %d: average length between pages = %.3f clicks%n",testCase, (float)(sum/pairs));
		}
	}
}

Sample Input Output for the Sample Input
1 2 2 4 1 3 3 1 4 3 0 0
1 2 1 4 4 2 2 7 7 1 0 0
0 0
Case 1: average length between pages = 1.833 clicks
Case 2: average length between pages = 1.750 clicks

Advertisements

About M Moniruzzaman
A passionate software engineer, have been developing applications on various platforms such as Android, iPhone, .Net (C#) technologies and web based ASP.NET, PHP, JavaScript, jQuery technologies for more than 10 years. Especially I have expertise on developing applications for Android and iPhone, as well as service oriented, client-server based applications where clients will be reside on Android/iPhone that communicate with WCF(.NET) service hosted on server. I have completed certification in Microsoft Certified Professional Developer (MCPD) on .Net 4 . I have completed my graduation in -- B.Sc. (Engineering) in Computer Science and Engineering, ShahJalal University of Science and Technology, Bangladesh. Thanks, M. Moniruzzaman (Zaman)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: