computer science homework

The purpose of this assignment is to implement graph algorithms for finding the shortest path from a source node to a destination node on a map.

Note: You CAN use ADTs such as TreeMap defined in Java library for this assignment. See TreeMap at https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html

For this programming assignment, you will implement a graph using an adjacency list representation. Your program will read a graph from a file called map.txt. The file is a text file where the first line contains two numbers. The first is the number of vertices n and the second is the number of edges m. After this line there will be n lines with three numbers representing node locations on a map. The first number represent the vertex ID, and the next two numbers representing (x, y) coordinates for the vertex. Then there will be m lines with three numbers representing edges and their weights. The first two numbers represent the source and destination vertex for the undirected edge. The third number is the weight for that edge. Your program should ask the user to enter the source and the destination and run Dijkstra’s shortest path algorithm to return the shortest path from the source to the destination. An example map.txt file would be:

4 5

1. 10 10 vertex 0’s location is at (10, 10)

2. 90 40

3. 30 10 vertex 1’s location is at (90, 40)

1. 2 1 edge connecting nodes 0 and 2 with weight 1

2. 2 5

3. 3 3

1 3 2

0 3 10 edge connecting nodes 0 and 3 with weight 10

This file represents a graph with 4 vertices, 5 edges, and has edges (0, 2) with weight 1, (1,2) with weight 5, (2,3) with weight 3, (1,3) with weight 2, (0,3) with weight 10. The graph is undirected; that is, for each edge (v, w), you should add v w and w v with the same weight in your program. Your program should output the shortest path (e.g., output the shortest path between vertex 0 and vertex 3 as a sequence of vertex labels 0, 2, 3). NOTE: The weight does NOT have to be an integer. In general the weight will be a floating point number.

• If your program does not compile, you receive zero points for this assignment.

• (20 points) You should implement the adjacency list data structure for the graph.

• (20 points) You should use your own implementation of Binary Heap for this assignment.

• (50 points) Be sure to test the correctness of your algorithms and implementations.

• (10 points) Your code will be graded based on whether or not it compiles, runs, produces the expected output, produces correct output, and your coding style.

Receive 20 bonus points if your program provides a GUI (graphic user interface) that shows the graph (nodes, edges, and edge weights) on a Java frame. The user can enter the source and the destination. The GUI then colors the shortest path. The basic 2D graphics GUI is given in

Map.java at isidore.

•Zip your project, and turn in the zip file to isidore.