Algorithm concepts

CSCI 651 Algorithm Concepts

Assignment 2

1. For this assignment, you will write code in any programming language of your choice to implement a simple undirected weighted graph data structure. You will also implement Djikstra’s algorithm to find the shortest path from a single specified node in the graph to every other node in the graph.

· The first part of the assignment requires you to write code that implements a graph data structure using an adjacency list representation. The code will prompt the user to enter the details of the graph and then create and print the adjacency list representation when it is done. It is up to you to decide how your program will collect all the information that is necessary to describe the graph. [30 Marks]

· In the second part of the assignment you will implement Djikstra’s shortest path algorithm. After creating the graph and printing out its adjacency list representation, the program will prompt the user for a random node in the graph. The program will then use Djikstra’s algorithm to find the shortest path between that node and every other node in the graph. The output should be in a table format as shown below [30 Marks]

End Node	Path	Distance
G	A -> B -> G	10

2. Run your program using the following graphs as sample input. Assume the weights represent the distance between nodes.

Graph 1

Graph 2

3. Use node a as the random node chosen in both graphs when you run Djikstra’s algorithm [30 Marks]

4. In your implementation you were asked to use an adjacency list representation for the graph. An adjacency matrix could have also been used. Discuss how you think a decision to use an adjacency matrix representation could have affected the ease of implementing Djikstra’s algorithm. [10 Marks]

Submit the above items by the due date via Blackboard. A detailed reported discussing your implementation along with results of running the code against the examples given (screenshots must be included). A detailed readme file that should explain how to run the code in a separate file. All your implemented code, also in separate files.