Assignment: Algorithm Concepts
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.
• In the second part of the assignment you will implement Djikstra's shortest path algorithm. After creating the graph and printing out itsadjacency 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.
|
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.
3. Use node a as the random node chosen in both graphs when you run Djikstra's algorithm.
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.
Format your assignment according to the following formatting requirements:
1. The answer should be typed, double spaced, using Times New Roman font (size 12), with one-inch margins on all sides.
2. The response also includes a cover page containing the title of the assignment, the student's name, the course title, and the date. The cover page is not included in the required page length.
3. Also include a reference page. The Citations and references should follow APA format. The reference page is not included in the required page length.
Attachment:- Graph.rar