Question 1

The file Names.txt contains the names of several individuals. The file Friends2.txt contains pairs of names of individuals that are friends and the distance in kilometres that each pair of friends live from each other. Each line contains a pair of friends separated by a comma followed by an integer (a number between 1 and 100) separated by another comma. We define the distance between any two individuals as the sum of the distances between the individuals that socially connects them (the distance will be infinity if two individuals are not socially connected). You have to implement Dijkstras Shortest Paths algorithm to determine the shortest distance between Yolanda and each of the other individuals in the file. Adapt your solution to the graph implementation below.

HINTS Dijkstras algorithm employs a priority queue to determine the order in which distances to vertexes must be updated. Java provides a built-in implementation of PriorityQueue with the following useful methods: boolean add(E e) Inserts the specified element into this priority queue. int size() Returns the number of elements in this collection. boolean remove(Object o) Removes a single instance of the specified element from this queue, if it is present. E poll() Retrieves and removes the head of this queue, or returns null if this queue is empty. Items in PriorityQueue must implement the Comparable interface. Please note that if you change the values of objects already in PriorityQueue, the items are not automatically reordered. It is thus necessary to remove and then add the item again to ensure that it is in the correct position (this is not an efficient or elegant solution, but the focus of this assignment is on the shortest path algorithm not the queue).

Names.txt:

Yolanda Larissa Fanya Jennee Sasha Katrine Othella Lorena Murielle Jillayne

Freinds2.txt:

Larissa,Fanya,82 Murielle,Yolanda,8 Jillayne,Jennee,12 Othella,Sasha,30 Lorena, Katrine, 26

Graph Class:

import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.util.ArrayList; import java.util.HashMap; import java.util.StringTokenizer;

public class GraphClass { private HashMap NameNumbers = new HashMap(); private ArrayList Names = new ArrayList(); boolean[][] matrix; public GraphClass() { loadNames(); matrix = new boolean[NameNumbers.size()][NameNumbers.size()]; loadFriends(); } public void loadFriends() { try { BufferedReader in = new BufferedReader(new FileReader(new File("Friends2.txt"))); while(in.ready()) { String S = in.readLine(); StringTokenizer line = new StringTokenizer(S,","); String Name1 = line.nextToken(); String Name2 = line.nextToken(); int Name1Number = NameNumbers.get(Name1); int Name2Number = NameNumbers.get(Name2); matrix[Name1Number][Name2Number] = true; matrix[Name2Number][Name1Number] = true; //This is not a directed graph so two entries are made in the table per edge }

} catch (Exception e) { e.printStackTrace(); System.exit(1); } } public void loadNames() { try { BufferedReader in = new BufferedReader(new FileReader(new File("Names.txt"))); int counter = 0; while(in.ready()) { String S = in.readLine(); NameNumbers.put(S, counter); Names.add(S); counter++; }

} catch (Exception e) { e.printStackTrace(); System.exit(1); } } }