Create a complex of connected rooms.  Read in the vertices and edges from files.  Allow the user to move around the complex by going North, South, East, and West.  Implement Dijkstra's algorithm to find the shortest path to a user selected room.  Have the option to show the adjacency list after running Dijkstra's.  Create a drawing of your complex.  Upload the following files to Ecampus:  (1) Drawing of complex, (2) Java source code, (3) vertex.txt, (4) edge.txt


1. Create a drawing of your complex.  It should have multiple paths to some rooms.  You can use PowerPoint for this.


2. Create vertex.txt and edge.txt

3. Create the Room class.  There are two variables used for Dijkstra's algorithm.

class Room
{
    String RoomName;
    Room North, South, East, West;
    boolean Visited;   // used for Dijkstra
    int Distance;      // used for Dijkstra

    Room (String theRoomName)
    {  RoomName = theRoomName;  }
}

4. Create the main program that reads in the vertices and edges.  The vertices go into the Vertex ArrayList.  Rooms are connected according to the edges.  You can start with the program below.

import java.io.*;
import java.util.*;
public class castle
{
	static ArrayList<Room> Vertex = new ArrayList<Room>();
	static ArrayList<Room> Path = new ArrayList<Room>();

	public static void main(String[] args) throws IOException
	{
		Scanner in = new Scanner(System.in);

		// read in vertices
		File file = new File("vertex.txt");
		Scanner infile = new Scanner(file);
		String Input = "";
		while (infile.hasNextLine())
		{
			Input = infile.nextLine();
			Vertex.add(new Room(Input));
		}
		System.out.println(Vertex.size() + " vertices read from file");

		// read in edges
		file = new File("edge.txt");
		infile = new Scanner(file);
		String From, Direction, To;
		int Count=0;
		while (infile.hasNext())
		{
			Count++;
			From = infile.next();
			Direction = infile.next();
			To = infile.next();
			// Uncomment this line to help debug runtime error reading edge.txt
			// System.out.println("From: " + From + " Direction: " + Direction + " To: " + To);
			
			// locate From Vertex in ArrayList
			int IndexFrom = 0;
			while (!Vertex.get(IndexFrom).RoomName.equals(From))
			{  IndexFrom++;  }
			// locate To Vertex in ArrayList
			int IndexTo = 0;
			while (!Vertex.get(IndexTo).RoomName.equals(To))
			{  IndexTo++;  }
			// create edge
			if (Direction.equals("North"))
			{
				Vertex.get(IndexFrom).North = Vertex.get(IndexTo);
				Vertex.get(IndexTo).South = Vertex.get(IndexFrom);
			}
			if (Direction.equals("South"))
			{
				Vertex.get(IndexFrom).South = Vertex.get(IndexTo);
				Vertex.get(IndexTo).North = Vertex.get(IndexFrom);
			}
			if (Direction.equals("East"))
			{
				Vertex.get(IndexFrom).East = Vertex.get(IndexTo);
				Vertex.get(IndexTo).West = Vertex.get(IndexFrom);
			}
			if (Direction.equals("West"))
			{
				Vertex.get(IndexFrom).West = Vertex.get(IndexTo);
				Vertex.get(IndexTo).East = Vertex.get(IndexFrom);
			}
		}
		System.out.println(Count + " edges read from file");
		System.out.println("Press <Enter> to Continue");
		Choice = in.nextLine();
	}
}

5. Write code to allow the user to move around the rooms, find the path, and print adjacency list.

To print the path, step through the Path ArrayList and print the RoomName.

To print the adjacency list after finding a path, step through the Vertex ArrayList and print the Distance and RoomName.

6.  Add Dijkstra's Shortest Path algorithm to your public class.  It requires static class variables Vertex and Path ArrayLists.  It will populate Distance and Visited variables in the Vertex Rooms.  It will clear add the shortest path Rooms to Path.

	static void Dijkstra(Room Start, Room Finish)
	{
		// set distance to all rooms (except for Start) to 1000 and visited = false
		for (int i=0; i<Vertex.size(); i++)
		{
			if (Vertex.get(i) == Start)
				Vertex.get(i).Distance = 0;
			else
				Vertex.get(i).Distance = 1000;  // set distance to "infinity"
			Vertex.get(i).Visited = false;
		}
		// Do Dijkstra - find Distance to each room
		Room Temp = Start;
		while (!Finish.Visited)
		{
			Temp.Visited = true;
			if (Temp.North!=null && !Temp.North.Visited && Temp.North.Distance > Temp.Distance+1)
				Temp.North.Distance = 1 + Temp.Distance;
			if (Temp.South!=null && !Temp.South.Visited && Temp.South.Distance > Temp.Distance+1)
				Temp.South.Distance = 1 + Temp.Distance;
			if (Temp.East!=null && !Temp.East.Visited && Temp.East.Distance > Temp.Distance+1)
				Temp.East.Distance = 1 + Temp.Distance;
			if (Temp.West!=null && !Temp.West.Visited && Temp.West.Distance > Temp.Distance+1)
				Temp.West.Distance = 1 + Temp.Distance;

			int Smallest = 1000;
			int SmallestIndex = 0;
			for (int i=0; i<Vertex.size(); i++)
			{
				if (!Vertex.get(i).Visited && Vertex.get(i).Distance < Smallest)
				{
					Smallest = Vertex.get(i).Distance;
					SmallestIndex = i;
				}
			}
			Temp = Vertex.get(SmallestIndex);
		}

		// populate Path ArrayList with Rooms of shortest path
		Temp = Finish;
		Path.clear();
		Path.add(0,Finish);
		while (Temp != Start)
		{
			int N = 1000, S = 1000, E = 1000, W = 1000;
			if (Temp.North != null)  N = Temp.North.Distance;
			if (Temp.South != null)  S = Temp.South.Distance;
			if (Temp.East != null)  E = Temp.East.Distance;
			if (Temp.West != null)  W = Temp.West.Distance;
			if (N < S && N < E && N < W)
				Temp = Temp.North;
			else if (S < E && S < W)
				Temp = Temp.South;
			else if (E < W)
				Temp = Temp.East;
			else
				Temp = Temp.West;
			Path.add(0,Temp);
		}
	}