## Description

Problem Description

Use the Dijkstra’s algorithm to find a shortest path in a directed graph from a vertex called “source” to all other vertices.

The solution should provide a value of the shortest path along with all intermediate vertices and weights on the path.

Remark: The Dijkstra’s algorithm provides a solution to the problem using a graph with positive weights.

• The project requirements

– Implement a graph data structure using a collection of adjacency lists such as it is represented in the textbook, see

the Figure 13.4, p. 603. You may use the C++ standard library classes, std::vector or std::list, when you

work with arrays or linked lists, respectively. At least the following graph operations should be included:

∗ inserting a new edge or a vertex: addEdge and addVertex.

∗ getting a list of all vertices.

∗ finding a vertex adjacent to a given one.

– Implement a minimum priority queue represented as a minimum binary heap; reuse your code from the programming

assignment #5. You can choose one of these options:

∗ a minimum binary heap without locator (90% of the maximum score)

∗ a minimum binary heap with locator (100% of the maximum score)

– Implement the Dijkstra’s algorithm using both the data structures: graph and minimum priority queue.

• The input output requirements

– Create a graph to be loaded from a user-defined data file. Use the following file format. (Here field descriptions are

in comments but you do not need to use comments in your data file.)

3 /* = the number of vertices */

/* start numerating vertices from 1 */

/* for a given vertex list all adjacent vertices and weights end by -1 */

/* format: vertex, adjacent_vertex, weight, adjacent_vertex, weight,…, -1 */

1 2 5 3 2 -1

2 3 4 -1

3 -1

-1 /* end of file */

– Display the graph in a similar format on the screen.

– Ask the user about the source and destination vertices in a graph.

– Display the value of the shortest path along with all the intermediate vertices with weights starting at the source and

ending at the destination. Example:

2 6 1

S —- A —- B —- D

Total wight of the shortest path from S to D = 9

– Display the total number of comparisons in order to compare the performance of the Dijkstra’s algorithm. You should

count

∗ the number of comparisons to remove minimum and restructure the heap after this operation

∗ the number of comparisons used to find/update and decrease element key value in the priority queue and its heap

representation.

2

• Report

In addition to the regular programming assignment report you should include answers to the following problems.

1. Write about the running time of the Dijkstra’s algorithm related to your implementation of Graph and Priority-Queue

ADT. Use the big-O notation to express the running time in order to compare performance of the implementation of

the Dijkstra’s algorithm with the most efficient complexity of this algorithm.

2. Discuss the implementation of the Dijkstra’s algorithm related to the representation of the Priority Queue ADT with

and without locator. What is the impact of implementing the Priority Queue with locator on the complexity of the

Dijkstra’s algorithm? Use the big-O notation to express the running time in each case.

3. Write about how you used the Priority Queue ADT to simplify coding and obtaining the most efficient implementation

of the Dijkstra’s algorithm if it applies to your implementation.

4. Test the Dijkstra’s algorithm on different graphs. In your report, find a solution for each graph by hand and provide

computational results.

5. Write about three real-life applications where you can use the Dijkstra’s algorithm.