COMP 182: Lab Assignment 9 - Shortest Distance in Graph

import GraphPackage .*; import ADTPackage .*; /** A driver that creates the graphs given in the Figure Finds the shortest path between two points in both graphs. */ public class Lab9 { private static UndirectedGraph < String > UDGraph ; private static StackInterface < String > path ; public static void main ( String [] args ) { UDGraph = new UndirectedGraph < String >(); path = new LinkedStack < String >(); String Sandwich = "Sandwich" ; String Falmouth = "Falmouth" ; String Barnstable = "Barnstable" ; String Hyannis = "Hyannis" ; String Chatham = "Chatham" ; String Orleans = "Orleans" ; String Truro = "Truro" ; String Provincetown = "Provincetown" ; // TODO: Create the graph in Figure // TODO: add each vertex to UDGraph // TODO: add each edge to UDGraph // TODO: employ shortest path method (in package) for each city pair UDGraph . addVertex ( Sandwich ); UDGraph . addVertex ( Barnstable ); UDGraph . addVertex ( Hyannis ); UDGraph . addVertex ( Falmouth ); UDGraph . addVertex ( Chatham ); UDGraph . addVertex ( Orleans ); UDGraph . addVertex ( Truro ); UDGraph . addVertex ( Provincetown ); UDGraph . addEdge ( Sandwich , Barnstable ); UDGraph . addEdge ( Barnstable , Hyannis ); UDGraph . addEdge ( Hyannis , Falmouth ); UDGraph . addEdge ( Hyannis , Chatham ); UDGraph . addEdge ( Chatham , Orleans ); UDGraph . addEdge ( Orleans , Barnstable ); UDGraph . addEdge ( Orleans , Truro ); UDGraph . addEdge ( Truro , Provincetown ); System . out . println ( "For the graph in the Figure, the shortest path from Sandwich to Falmouth is" ); // TODO: displaypath method UDGraph . getShortestPath ( Sandwich , Falmouth , path ); displayPath ( path );

// TODO: print other two city pairs System . out . println ( "For the graph in the Figure, the shortest path from Sandwich to Chatham is" ); UDGraph . getShortestPath ( Sandwich , Chatham , path ); displayPath ( path ); System . out . println ( "For the graph in the Figure, the shortest path from Falmouth to Orleans is" ); UDGraph . getShortestPath ( Falmouth , Orleans , path ); displayPath ( path ); } // end main public static void displayPath ( StackInterface < String > stack ) { while (! stack . isEmpty ()) { System . out . println ( stack . pop ()); } // end while System . out . println (); } // end displayPath } // end Driver