import java.util.LinkedList;
import java.util.ListIterator;
public class AdjList
{
private LinkedList list[];
private int num_vertices;
/*
* Constructor: Allocates right amount of space
*/
public AdjList(int num_vertices)
{
this.num_vertices = num_vertices;
list = new LinkedList[num_vertices];
/*
* initialize all of the linked lists in the array
*/
for (int index = 0; index < num_vertices; index++)
{
list[index] = new LinkedList();
}
}
/*
* add an edge to the graph
*/
public void addEdge(Edge new_edge)
{
list[new_edge.getStartVertex()].addFirst(new_edge);
}
/*
* remove a directed edge from the graph
*/
public void removeEdge(Edge remove_me)
{
list[remove_me.getStartVertex()].remove(remove_me);
}
/*
* Provide an edge (get me) with a start and finish, get
* back an edge with the start, finish, and cost
*/
public Edge getEdge (Edge get_me)
{
int index = list[get_me.getStartVertex()].indexOf(get_me);
return (Edge) list[get_me.getStartVertex()].get(index);
}
/*
* Returns an iterator that contains the Edges leading to
* adjacent nodes
*/
public ListIterator getAdjacencies (int vertex)
{
return list[vertex].listIterator();
}
/*
* Feel free to make this prettier, if you'd like
*/
public String toString()
{
String temp = "";
for (int index=0; index < num_vertices; index++)
{
temp = temp + index + ": " + list[index].toString() + "\n";
}
return temp;
}
}
public class Edge
{
/*
* This class models an edge from vertex X to vertex Y -- pretty
* straightforward.
*
* It is a little wasteful to keep the starting vertex, since the
* adjacency list will do this for us -- but it makes the code
* neater in other places (makes the Edge independent of the Adj. List
*/
private int vertex_from;
private int vertex_to;
private int cost;
public Edge(int vertex_from, int vertex_to, int cost)
{
this.vertex_from = vertex_from;
this.vertex_to = vertex_to;
this.cost = cost;
}
public Edge(int vertex_from, int vertex_to)
{
this.vertex_from = vertex_from;
this.vertex_to = vertex_to;
this.cost = 0;
}
int getStartVertex()
{
return vertex_from;
}
public int getDestinationVertex()
{
return vertex_to;
}
public int getCost()
{
return cost;
}
/*
* considers two edges equal if they go to the same
* vertex, regardless of their weight
*/
public boolean equals(Object other_edge)
{
return ( ((((Edge)other_edge).vertex_from ==
((Edge)this).vertex_from)) &&
((((Edge)other_edge).vertex_to ==
((Edge)this).vertex_to)) );
}
/*
* Feel free to make this prettier, if you'd like.
*/
public String toString()
{
return "{" + vertex_from + "," + vertex_to + "," + cost + "}";
}
}
import java.io.*;
import java.util.*;
/*
* This class models a collection fo cities and roads.
* It uses two graphs. One which keeps the distance of the roads
* in miles as the cost of the edges. The other of which keeps the
* expected travel time, in minutes, as the cost of the edges.
*/
class RoadMap
{
private class DijTableEntry
{
public boolean known = false;
public int distance = Integer.MAX_VALUE, path = -1;
public String toString(){
String s = "";
if(known)s+="known";
else s+="unknown";
s+= " Distance: "+distance+" Path: "+path+"\n";
return s;
}
}
private DataReader mapFile; // File abstraction for input file
private String cityName[]; // City number to name mapping table
private AdjList distanceMap; // Graph representing map w/cost as distance
private AdjList timeMap; // Graph representing map w/cost as travel time
private int getCityNumber (String givenCityName)
{
for (int index=0; index < cityName.length; index++)
if (cityName[index].equals(givenCityName))
return index;
return -1;//not found
}
/*
* This creates the distanceMap and timeMap from a properly
* formatted input file
*/
public RoadMap (String mapFileName)
{
try
{
mapFile = new DataReader (mapFileName);
int numCities = mapFile.readInt();
distanceMap = new AdjList(numCities);
timeMap = new AdjList(numCities);
cityName = new String [numCities];
// Read city names into name:number mapping
for (int index=0; index < numCities; index++)
cityName[index] = mapFile.readWord();
}
catch (Exception e)
{
// An error -- not much to do.
System.out.println (e);
return;
}
try
{
while (true)
{
String startCity = mapFile.readWord();
String destinationCity = mapFile.readWord();
int distance = mapFile.readInt();
int time = mapFile.readInt();
distanceMap.addEdge(new Edge( getCityNumber(startCity),
getCityNumber(destinationCity),
distance));
timeMap.addEdge(new Edge ( getCityNumber(startCity),
getCityNumber(destinationCity),
time));
}
}
catch (EOFException e)
{ } // Normal exit -- no more roads to map
catch (Exception e)
{
// A real error -- not much to do.
System.out.println (e);
System.exit (-1);
}
}
public DijTableEntry[] dijkstra (String start, boolean distanceNotTime)
{
AdjList a = timeMap;
if(distanceNotTime)a = distanceMap;
int size = cityName.length;
DijTableEntry[] dijTable = new DijTableEntry[size];
for(int i=0;i<size;i++)dijTable[i] = new DijTableEntry();
//initialize the table
//set the initial node
int start_node = getCityNumber(start);
if(start_node==-1){
System.err.println("Error, bad starting city");
return null;
}
dijTable[start_node].known = false;
dijTable[start_node].distance = 0;
dijTable[start_node].path = -2;
//use this marker instead of -1 so we can distinguish
//the starting node later on
//potentially for each node, expand the closest one to the start
int next;
while((next = getMinDistance(dijTable)) != -1){
expand(next, dijTable, a);
}
return dijTable;
}
//helper function to get the closest remaining node
private int getMinDistance(DijTableEntry []dijTable){
//initialize to the 'error node'
int minnode = -1;
//initialize to the same as the initial distance for node
int mindist = Integer.MAX_VALUE;
//check every unknown node and get the one with
//the smallest distance
for(int i=0;i<dijTable.length;i++){
if(!dijTable[i].known && dijTable[i].distance < mindist){
minnode = i;
mindist = dijTable[i].distance;
}
}
return minnode;
}
//helper function to expand a node and update it's neighbors
private void expand(int node, DijTableEntry []dijTable, AdjList graph){
//first mark this node as known
dijTable[node].known = true;
//get the length of the shortest path to this node
int costToNode = dijTable[node].distance;
//loop over all neighboring nodes
for(ListIterator li = graph.getAdjacencies(node);li.hasNext();){
Edge e = (Edge)(li.next());
int neighbor = e.getDestinationVertex();
//if the neighbor has not been expanded and the
//cost via this node is cheaper then update it
//(technically we don't need to check if it's marked
// since this path must be at least as big as the optimal one)
if(!dijTable[neighbor].known &&
costToNode + e.getCost() < dijTable[neighbor].distance){
dijTable[neighbor].distance = e.getCost() + costToNode;
dijTable[neighbor].path = node;
}
}
}
//helper to get the distance from i to j
private int getdist(int i, int j){
Edge e = new Edge(i, j);
e = distanceMap.getEdge(e);
if(e==null)return Integer.MAX_VALUE;
return e.getCost();
}
//helper to get the time from i to j
private int gettime(int i, int j){
Edge e = new Edge(i, j);
e = timeMap.getEdge(e);
if(e==null)return Integer.MAX_VALUE;
return e.getCost();
}
public void printPath (DijTableEntry []dijTable, String finish)
{
//first check the parameters
if(dijTable==null){
System.err.println("Error, Dijkstra's algorithm failed");
return;
}
int node = getCityNumber(finish);
if(node == -1){
System.err.println("Error: bad finishing city");
return;
}
if(dijTable[node].path==-1){
System.out.println("No path to "+finish);
return;
}
if(dijTable[node].path==-2){
System.out.println("Start and finish at "+finish);
return;
}
//it is easy to get the cities in reverse order,
//so we'll put them in a stack to print in reversed reverse order
Stack s = new Stack();
s.push(cityName[node]);//put in the last city
//traverse the table backwards until we reach a node without a
//predecessor (eg the starting node)
while(dijTable[node].path >= 0){
//push onto the stack a string including the name of
//city and weight to reach the next node
s.push(cityName[dijTable[node].path]+
" --("+getdist(dijTable[node].path, node)
+"mi, "+gettime(dijTable[node].path, node)
+"h)--> ");
//and repeat from the predecessor
node = dijTable[node].path;
}
//check if we stopped prematurely
if(dijTable[node].path != -2){
System.err.println("Error, dijkstra produced a bad table");
return;
}
//print out the reversed path, which is now the correct order
while(!s.isEmpty())
System.out.print((String)(s.pop()));
System.out.println();
}
public String toString()
{
return "Distance\n\n" + distanceMap.toString() + "\n\n" +
"Time\n\n" + timeMap.toString() + "\n\n";
}
public static void main (String []args)
{
if(args.length < 2){
System.out.println("Please specify a data file, start city, and end city");
return;
}
RoadMap r = new RoadMap(args[0]);
System.out.println("Computing smallest time");
r.printPath(r.dijkstra(args[1] , false), args[2]);
System.out.println("Computing shortest distance");
r.printPath(r.dijkstra(args[1] , true), args[2]);
}
}