The task is:
Find the shortest path between two cities. Cities are connected with one-way roads. Cities are present inside a .txt file in such manner:
// From // // To // // Distance //
e.g.:
London Glasgow 180
Manchester Liverpool 80
York Cambridge 415
York Manchester 260
Glasgow York 315
Glasgow Manchester 315
Given a source city S and target city T, find the shortest path. Calculate the distance and retrieve the taken path.
Problem is: I am not allowed to use any STL container at all. Cannot use containers such as std::list, std::vector, std::pair, std::set, etc. I am, however, able to use my own implemented dynamic data structures.
I'm clueless which data structures should I implement and how to implement them. Also, should I use priority queue, or a heap, or something else? Also wondering about adjacency list or adjacency matrix.
I don't really care if the solution is well-optimized or not.
I have been googling much, but all Dijkstras algorithms implementations I found use plenty of STL containers, that I'm not allowed to use.
Any tips, hints or links are appreciated. Thank you.
To code Dijkstra's shortest path algorithm you only need to implement a priority queue (min heap).
I recommend heap above all. The implementation of a set involves a (almost) balanced binary search tree like AVL or Red-Black Tree or Treap (Cartesian Tree), such codes are way harder by several orders of magnitude than implementing a heap. Also, all these solutions have the same running time O(log n) so easier to code solution come first.