gistfile1.java

/**
	 * calculates the shortest path between two persons in the social graph
	 * @param p1 person
	 * @param p2 person
	 * @return shortest path between two persons
	 */
	public Person[] shortestPath(Person p1, Person p2) {

		if (p1 == null || p2 == null) {
			throw new IllegalArgumentException();
		}

		int[][] matrix = calculateDistanceMatrix();
		//System.out.println(MathUtil.matrixToString(matrix));
		Person[] persons = getPersons();
		int startIndex = getProfileNumber(getProfile(p1));
		int targetIndex = getProfileNumber(getProfile(p2));
		int length = matrix[startIndex][targetIndex];

		if (length == Integer.MAX_VALUE) {
			return null;
		}

		if (areFriends(p1, p2)) {
			Person[] path = {p1, p2};
			return path;
		}

		int currentLength = length - 1;
		Person[] path = new Person[length + 1];

		// we already know the start and end of the path
		path[0] = p1;
		path[length] = p2;

		int cur = startIndex; // current base-node: p1
		// build path
		for (int j = 1; j < path.length; j++) {
			for (int i = 0; i < matrix[cur].length; i++) {
				if (matrix[cur][i] == 1) {
					for (int k = 0; k < matrix[i].length; k++) {
						// if distance between current base-node
						// and current node equals our current path-length
						// add it to the path
						if (matrix[i][targetIndex] == currentLength) {
							path[j] = persons[i];
							currentLength--;
							// sets new base-node
							cur = i;
						}
					}
				}
			}
		}

		return path;

	}