# ECE 365 Programming Assignment 3 Dijkstra’s Algorithm solution

\$30.00

Original Work ?

## Description

You are going implement Dijkstra’s algorithm to solve the single-source shortest-path problem. The program will determine the shortest path in a specified graph from a specified starting vertex to each other vertex in the graph. In order to do this efficiently, your program should use the binary heap class that you created for the previous assignment.

Your program should start by asking the user to enter the name of a file specifying the graph.Every row in the input file represents an edge in the graph.Each rowconsists oftwo string ids representing the source vertex and destination vertex of the edge (in that order) followed by an integer representing the cost (a.k.a. distance or weight) of the edge.The rows will contain no leading or trailing whitespace, single spaces will separate fields, and all rows will end with a single Unix-style newline character.All vertex ids will consist only of lowercase and capital letters and digits. All edge costs will be positive integers less than one million. A vertex exists if it is the source or the destination of any edge.The source vertex of an edge will never be the same as the destination vertex, but it is possible that multiple edges might connect the same vertices.Your program may assume that the file, if it can be opened, is valid. You are not required to include error checks for invalid file formats; you may if you wish, but I will not check for this.

Once the program is finished reading in the graph, the user should be prompted to enter the id of a starting vertex. The user should be re-prompted until they enter a valid index (i.e., a string id representing a vertex that exists in the graph). The program should then apply Dijkstra’s algorithm to determine the shortest path to each node from the specified starting vertex. The implementation should rely on the binary heap classthat you created for the previous assignment. (The heap class, of course, relies on the hash class you created for the first assignment, and you will also likely rely on the hash class for a couple of other purposes as well.) When the algorithm has finished determining the shortest path to each node, your program should output the CPU time, in seconds, that was spent executing the algorithm.

The program should then ask the user for the name of an output file. The output file should contain one row for every vertex that exists in the graph, with vertices listed in the same order that they first appear in the input file. Each row in the output file should contain a vertex id followed by a colon, a single space, and then the shortest distance from the specified starting vertex to the given vertex. All of these distances are guaranteed to be less than one billion. After the distance, the row should contain one space, a left bracket, the path from the starting vertex to the current vertex, a right bracket, and finally a single Unix-style newline character. Vertices in the path should be separated by a comma followed by a single space. There should not be any space or comma before the first vertex in the path (the specified starting vertex) or after the last vertex in the path.If there is no path from the specified starting vertex to any existing vertex in the graph, the corresponding output row should contain the vertex id followed by a colon, a single space, and then the text “NO PATH” followed by a single Unix-style newline character. You must follow these instructions exactly.

In class, we stepped through Dijkstra’s algorithm for the following graph, which came from Figure 9.20 in the textbook:

The file representing this graph might look like this:

v1 v2 2

v1 v4 1

v2 v4 3

v2 v5 10

v3 v1 4

v3 v6 5

v4 v3 2

v4 v5 2

v4 v6 8

v4 v7 4

v5 v7 6

v7 v6 1

Any permutation of the rows representing edges in this file would designate the same graph (but the order of rows in the output file might be different).Assume a file called graph.txt exists, containing the data shown above. Then a sample run of your program might look like this:

Enter name of graph file: graph.txt

Enter a valid vertex id for the staring vertex: v1

Total time (in seconds) to apply Dijkstra’s algorithm: 0.000

Enter name of output file: out.txt

The prompts to the user may vary, but the file out.txt should look exactly like this:

v1: 0 [v1]

v2: 2 [v1, v2]

v4: 1 [v1, v4]

v5: 3 [v1, v4, v5]

v3: 3 [v1, v4, v3]

v6: 6 [v1, v4, v7, v6]

v7: 5 [v1, v4, v7]

If the user specifies the same graph file but entersv5 as the id of the starting vertex, then the output file should look exactly like this:

v1: NO PATH

v2: NO PATH

v4: NO PATH

v5: 0 [v5]

v3: NO PATH

v6: 7 [v5, v7, v6]

v7: 6 [v5, v7]