[Solved]Know Much Time Might Get Extension Please Help Code C Cse310 Project 2 Navigating Via Dij Q37088152
I know it is not much time but I might get an extension soplease help. Code has to be in C++.
CSE310 Project 2: A Navigating via Dijkstra’s Algorithm
Due: Friday, 04/19/2019
The zip file should contain a set of files that are absolutelynecessary to compile and execute your program. If you program doesnot compile and work on general.asu.edu, you will receive 0 on thisproject In your first programming project, you have implemented themin-heap data structure and its associated functions. In thisprogramming project, you have to expand the fields of ELEMENT tocontain other fields as needed. Then you will add a module toimplement Dijkstra’s shortest path algorithm. Your program shouldbe able to read in a graph, and build the edge adjacency list ofthe graph. Note that the edge adjacency list is an array (indexedby the vertices) of singularly linked lists, where the listaccording to a node v denotes the outgoing neighbors of node v.When given a source-destination pair, your program should computethe shortest path from the source to the destination, and outputthe result as required. Dijkstra’s shortest path algorithm uses amin-heap of the vertices of the graph, where the key value at anode is the currently known distance from the source to the givennode. You have to define the data types as needed. You shouldimplement a module that takes the following commands from thekey-board and feed to the main program:
• E
• I
• W
• C s t iFlag
On reading E, the program stops.
On reading I, the program reads in an edge weighted directedgraph from file Ginput.txt, builds the adjacency lists, and waitsfor the next command.
The file Ginput.txt is a text file. The first line of the filecontains two integers n and m, which indicate the number ofvertices and the number of edges of the graph, respectively. It isfollowed by m lines, where each line contains three integers: u,v,and w. These three integers indicate the information of an edge:there is an edge pointing from u to v, with weight w . Please notethat the vertices of the graph are indexed from 1 to n (not from 0to n −1).
On reading W , the program writes the graph information to thescreen, and waits for the next command. The screen output format ofW is as follows: The first line should contain two integers, n andm , where n is the number of vertices and m is the number of edges.It should be followed by n lines, where each of these n lines hasthe following format:
u : (v1, w1); (v2, w2);. . .; (vk, wk)
On reading C s t 0, the program runs Dijkstra’s shortest pathalgorithm to compute a shortest s-t path, and prints out the lengthof this shortest path to the screen, and waits for the nextcommand. The information printed to the screen should be of theformat: LENGTH: l, where l is the path length.
On reading C s t 1, the program runs Dijkstra’s shortest pathalgorithm to compute a shortest s -t path, and prints out the pathof this shortest path to the screen, and waits for the nextcommand. The information printed to the screen should be of theformat: PATH:s, v1, v2, . . . , t, where the vertices listed givesout the path computed. Please note that your program should read inonly one graph, but may be asked to compute s-t shortest paths fordifferent pairs of s and t. Therefore, during the computation ofthe s – t shortest path, your program should not modify the givengraph. You should use modular design. At the minimum, you shouldhave
• the main program as main.cpp and the corresponding main.h;
• the heap functions heap.cpp and the corresponding heap.h;
• the graph functions graph.cpp and the correspondinggraph.h;
• various utility functions util.cpp and the correspondingutil.h.
Grading policies:
(10 pts) Modular design: You should have a pair ofimplementation and header files for each of the following: utility,heap, graph.
(10 pts) Documentation: You should provide sufficient commentabout the variables and algorithms. You also need to provide aREADME file describing what you are trying to achieve in thisproject.
(10 pts) Graph I/O: The program reads the graph from a file intomemory and outputs the necessary information.
(30 pts) Your program should produce the correct output for aposted set of test cases.
(30 pts) Your program should produce the correct output for anunposted set of test cases.
———————————————————————-
Ginput1.txt
3 6
2 3 2
2 1 6
2 1 4
1. 2 3
1. 1 2
2. 1 8
Ginput2.txt
7 11
5 6 13
2 2 3
1. 2 7
1. 4 2
3 2 2
4 1 2
6 7 2
4 5 1
1. 1 4
2. 3 1
3. 5 9
——————————————————————-
CSE310 Project02 Test Cases
Test Case 1:
There is no file named Ginput.txt
Commands are:
I
Output:
I
COMMAND: I.
There was a problem opening file Ginput.txt for reading.
Test Case 2:
Content of Ginput.txt
3 6
2 3 2
2 1 6
2 1 4
1 2 3
1 1 2
2 1 8
Commands are:
W
Output:
W
COMMAND: W.
Error: There is no graph to print.
Test Case 3:
Content of Ginput.txt
3 6
2 3 2
2 1 6
2 1 4
1 2 3
1 1 2
2 1 8
Commands are:
c 3 4 1
C 3 4 0
Output:
c 3 4 1
COMMAND: c 3 4 1.
Error: There is no graph to run Dijkstra’s algorithm on.
C 3 4 0
COMMAND: C 3 4 0.
Error: There is no graph to run Dijkstra’s algorithm on.
Test Case 4:
Content of Ginput.txt
3 6
2 3 2
2 1 6
2 1 4
1 2 3
1 1 2
Commands are:
i
Output:
i
COMMAND: i.
Error: The number of edges is less than as specified in thebeginning of the file.
Test Case 5:
Content of Ginput.txt (Note the number of edges specified in thefirst line vs. the actual
number of edges provided!)
3 6
2 3 2
2 1 6
2 1 4
1 2 3
1 1 2
2 1 8
1 3 5
Commands are:
I
W
Output:
I
COMMAND: I.
W
COMMAND: W.
3 6
1 : (2, 3); (1, 2)
2 : (3, 2); (1, 6); (1, 4); (1, 8)
3 :
Test Case 6:
Content of Ginput.txt
3 6
2 3 2
2 1 6
2 1 4
1 2 3
1 1 2
2 1 8
Commands are:
I
W
I
C 1 1 0
C 1 1 1
Output:
I
COMMAND: I.
W
COMMAND: W.
3 6
1 : (2, 3); (1, 2)
2 : (3, 2); (1, 6); (1, 4); (1, 8)
3 :
I
COMMAND: I.
C 1 1 0
COMMAND: C 1 1 0.
LENGTH: 0
C 1 1 1
COMMAND: C 1 1 1.
PATH: 1
Test Case 7:
Content of Ginput.txt
3 6
2 3 2
2 1 6
2 1 4
1 2 3
1 1 2
2 1 8
Commands are:
I
C 2 1 1
W
C 2 1 0
W
Output:
I
COMMAND: I.
C 2 1 1
COMMAND: C 2 1 1.
PATH: 2, 1
W
COMMAND: W.
3 6
1 : (2, 3); (1, 2)
2 : (3, 2); (1, 6); (1, 4); (1, 8)
3 :
C 2 1 0
COMMAND: C 2 1 0.
LENGTH: 4
W
COMMAND: W.
3 6
1 : (2, 3); (1, 2)
2 : (3, 2); (1, 6); (1, 4); (1, 8)
3 :
Test Case 8:
Content of Ginput.txt
3 6
2 3 2
2 1 6
2 1 4
1 2 3
1 1 2
2 1 8
Commands are:
I
W
C 1 3 0
C 3 1 0
C 1 3 1
C 3 1 1
W
I
W
Output:
I
COMMAND: I.
W
COMMAND: W.
3 6
1 : (2, 3); (1, 2)
2 : (3, 2); (1, 6); (1, 4); (1, 8)
3 :
C 1 3 0
COMMAND: C 1 3 0.
LENGTH: 5
C 3 1 0
COMMAND: C 3 1 0.
Sorry, node 1 is not reachable from node 3.
C 1 3 1
COMMAND: C 1 3 1.
PATH: 1, 2, 3
C 3 1 1
COMMAND: C 3 1 1.
Sorry, node 1 is not reachable from node 3.
W
COMMAND: W.
3 6
1 : (2, 3); (1, 2)
2 : (3, 2); (1, 6); (1, 4); (1, 8)
3 :
I
COMMAND: I.
W
COMMAND: W.
3 6
1 : (2, 3); (1, 2)
2 : (3, 2); (1, 6); (1, 4); (1, 8)
3 :
Test Case 9:
Content of Ginput.txt
3 6
2 3 2
2 1 6
2 1 4
1 2 3
1 1 2
2 1 8
Commands are:
I
C 1 3 0
C 1 3 7
c 10 20 1
C 10 20 30
w
Output:
I
COMMAND: I.
C 1 3 0
COMMAND: C 1 3 0.
LENGTH: 5
C 1 3 7
COMMAND: C 1 3 7.
Error: Invalid flag value.
c 10 20 1
COMMAND: c 10 20 1.
Error: One or more of the nodes is invalid.
C 10 20 30
COMMAND: C 10 20 30.
Error: One or more of the nodes is invalid.
Error: Invalid flag value.
w
COMMAND: w.
3 6
1 : (2, 3); (1, 2)
2 : (3, 2); (1, 6); (1, 4); (1, 8)
3 :
Test Case 10:
Content of Ginput.txt
7 11
5 6 13
2 2 3
1 2 7
1 4 2
3 2 2
4 1 2
6 7 2
4 5 1
1 1 4
2 3 1
3 5 9
Commands are:
I
W
C 1 7 1
C 1 7 0
C 7 1 0
C 5 6 0
C 5 6 1
C 2 6 1
C 2 6 0
C 4 2 0
C 4 2 1
C 5 7 0
C 5 7 1
C 4 7 0
C 4 7 1
W
E
Output:
I
COMMAND: I.
W
COMMAND: W.
7 11
1 : (2, 7); (4, 2); (1, 4)
2 : (2, 3); (3, 1)
3 : (2, 2); (5, 9)
4 : (1, 2); (5, 1)
5 : (6, 13)
6 : (7, 2)
7 :
C 1 7 1
COMMAND: C 1 7 1.
PATH: 1, 4, 5, 6, 7
C 1 7 0
COMMAND: C 1 7 0.
LENGTH: 18
C 7 1 0
COMMAND: C 7 1 0.
Sorry, node 1 is not reachable from node 7.
C 5 6 0
COMMAND: C 5 6 0.
LENGTH: 13
C 5 6 1
COMMAND: C 5 6 1.
PATH: 5, 6
C 2 6 1
COMMAND: C 2 6 1.
PATH: 2, 3, 5, 6
C 2 6 0
COMMAND: C 2 6 0.
LENGTH: 23
C 4 2 0
COMMAND: C 4 2 0.
LENGTH: 9
C 4 2 1
COMMAND: C 4 2 1.
PATH: 4, 1, 2
C 5 7 0
COMMAND: C 5 7 0.
LENGTH: 15
C 5 7 1
COMMAND: C 5 7 1.
PATH: 5, 6, 7
C 4 7 0
COMMAND: C 4 7 0.
LENGTH: 16
C 4 7 1
COMMAND: C 4 7 1.
PATH: 4, 5, 6, 7
W
COMMAND: W.
7 11
1 : (2, 7); (4, 2); (1, 4)
2 : (2, 3); (3, 1)
3 : (2, 2); (5, 9)
4 : (1, 2); (5, 1)
5 : (6, 13)
6 : (7, 2)
7 :
E
COMMAND: E.
The program is going to be terminated.
Expert Answer
Answer to I know it is not much time but I might get an extension so please help. Code has to be in C++. CSE310 Project 2: A Navig… . . .
OR
