C++ project on Dijkstra's algorithm using STL data structures
Below is the project description. Attached is the more detailed project description and also the input and output files.
In this project you will be implementing Dijkstra's algorithm for finding the shortest path tree in a weighted undirected graph. The goals of this project are to become better acquainted with:
implementing graph based algorithms;
using hashmaps and priorities queues in algorithms;
working with and around the data structures provided by the STL.
Your implementation of Dijkstra's algorithm must be based on the data structures provided by the STL, and must run in O((n+m)log n) time when run on a graph with n vertices and m edges.
This project will be making heavy use of hashmaps. In the STL hashmaps have the type std::unordered_map<K, V>, where K is the key type and V is the value type. If you wish to use a std::unordered_map with types you have created, you may need to overload the appropriate operators and functions.
The priority queue data structure is central to Dijkstra's algorithm. In the STL the type of a priority queue is std::priority_queue<T, Container, Compare>, where T is the type of items stored in the priority queue, Container is the type of the underlying container for items (normally std::vector<T>), and Compare specifies how items are compared.
Template parameter: T
The type T must implement the following operators: <, >, <=, >=, ==, !=, see operator overloading for tips. This will be a class or struct that you define to hold both a priority and a vertex. The comparison operators should be based on the just the priority.
Template parameter: Container
In this project we will just use std::vector for this parameter.
Template parameter: Compare
The STL priority queue is a max priority queue by default, i.e., it returns items of higher priority before items with lower priorities. For Dijkstra's algorithm we need a min priority queue. We could work around this problem by simply negating all of the priorities, but the more appropriate way of handling this situation is to use std::greater<void> for the Compare template parameter.
You may use any graph implementation that meets the required performance, but I would suggest you use std::unordered_map<V,std::unordered_map<V,W>> where V is the type of a vertex and W is the type of an edge weight. In this project V is std::string and W is double. This style of resenting graphs is popular in python (an essay on the topic), and has similar syntactic benefits in C++. You may want to create some helper functions for working with the graph, but this is not necessary.
The pseudocode for Dijkstra's algorithm is given below. This version of the algorithm does not use the decrease key operation, as the STL priority queue does not implement such a method. Instead we simply re-add the vertices to the priority queue when the priority is decreased.
def dijkstra(graph, source):
// Setup data structures
distance = empty hashmap taking vertices to distances
parent = empty hasmap taking vertices to vertices
pqueue = empty priority queue
// Initialize data structures
for each vertex v in G:
distance[v] = infinity
distance[source] = 0
pqueue.add(source, 0) // first arg is vertex, second arg is priority
// Main algorithm loop
while pqueue is not empty:
v = pqueue.pop_min()
for each neighbor u of v:
new_distance = distance[v] + length of the edge from v to u
if new_distance < distance[u]:
distance[u] = new_distance
parentpu[u] = v
// Return hashmaps
return distance, parent
The input and output format for this project are strict. You may assume that the input files are exactly as described and we will assume the same about your output files.