1

I am trying to implement Dijkstra's shortest path algorithm using C++ and STL. Since STL's priority queues do not support a decrease-key operation, I decided to use regular ordered sets. My algorithm is almost identical to this one.

However, I have some concerns. Namely, the ordering of the edges in the set will depend both upon the vertex number of the destination and the weight (as the regular relational operators of std::pair will be used). I do believe that it should only depend on the weight. If I were to declare the set by using a custom comparator which would compare only the weights, how would I make std::set::erase work, as it is needed to erase the edges between the same vertices but with greater weight?

Are there any other flaws that you guys can think of? Or do you perhaps have some better ideas than using std::set?

Have a great Sunday, everyone.

d125q
  • 1,666
  • 12
  • 18
  • possible duplicate of [Performance of Dijkstra's algorithm implementation](http://stackoverflow.com/questions/6319149/performance-of-dijkstras-algorithm-implementation) – πάντα ῥεῖ May 11 '14 at 11:52
  • If it's not for a school project use boost.graph http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/index.html – 101010 May 11 '14 at 12:45
  • Regarding the `std::set`-question, have a look at [this](http://www.lafstern.org/matt/col1.pdf). – davidhigh May 11 '14 at 13:32
  • @d125q I have an efficient implementation that does not make use of set if you want the code do comment – akashchandrakar Jun 12 '15 at 09:33

1 Answers1

1

Your question seem to confuse the technical implementation and the algorithm.

First, on the technical side, for std::set you seem to need a special ordering as well as an erasement of certain elements. The ordering can be changed by a custom comparator, for example see here. However, I would not order only by the weights, as there might be duplicates. Just put the weights in the component of std::pair which has a higher priority (--the first component).

Next, in order to erase an element, you must first be sure which one, which is done by providing an iterator pointing to that element. This step is not at all influenced by your custom comparison function.

Quickly summarizing: you should (i) find out which elements need to be erased exactly, (ii) find the corresponding iterators via std::set::find and (iii) erase them. To me it seems as if the first point would be the problem here.

Community
  • 1
  • 1
davidhigh
  • 14,652
  • 2
  • 44
  • 75
  • Indeed my question confused the technical implementation and the algorithm. But anyhow, the problems I was having stemmed from the fact that my value declared as “infinity” was in fact not large enough. Yeah, I doubt you can think of a more miserable thing. – d125q May 11 '14 at 17:11
  • For such cases, you can use, e.g., `std::numeric_limits::max()` (this gives you the largest possible number) or `boost::optional` (this implements a whole new concept to the initialization process--variables may also be uninitialized). Or simply take 2*infinity ;-) – davidhigh May 11 '14 at 20:07