CODEWITHSUNDEEP
c++data-structuresdijkstraadjacency-matrixadjacency-list
weno
weno

Reputation: 856

C++ - what data structures for Dijkstra's should I use?

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.

Upvotes: 1

Views: 931

Answers (1)

Eloy Pérez Torres
Eloy Pérez Torres

Reputation: 1177

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.

Upvotes: 1

Related Questions