Implementation of Dijkstra's shortest path algorithm

This is my code that implements Dijkstra's single source shortest path algorithm, which is called multiple times to recalculate after graph changes. the graph is a road system of a city and shortest path needs to be calculated when certain roads close one at a time.

I am looking for advice on the following:

• Will this read better if it is object oriented? I guess that is a resounding yes. What kind of classes make sense? (one for adjacency list, one for list of closed roads and so on?) Is this design effort worth the time on coding competitions?

• What are other glaring design errors in my code? (I know global vars are one. Sometimes I need multiple return values - do I make a struct for each of such type of return values? Is there a less tedious design?)

I hope the question is specific enough. If not, I can add more details.

```
#include
#include
#include
#include

using namespace std;

#define ulong unsigned long
#define INFINITY (ulong)-1

typedef struct {
ulong nbr;
ulong cost;
} ADJ_LIST_NODE;

typedef struct {
ulong shortest_dist;
ulong predecessor;
} SP_FOUND_NODE;

typedef struct {
ulong vertex;
ulong dist;
ulong predecessor;
} SP_ESTIMATE_NODE;

typedef struct {
ulong v1;
ulong v2;
} ROAD;

class SPEstimateNodeCompare {
public:
bool operator()(const SP_ESTIMATE_NODE& a, const SP_ESTIMATE_NODE& b) {
return a.dist > b.dist;
}
};

vector > city_adj_list;
ulong n_cities, m_roads;
ulong src, dest;
ulong q_broken_roads;
vector broken_road_list;

map sp_found;
priority_queue, SPEstimateNodeCompare > sp_estimate_q;
map estimate_distances;

void read_input() {
cin >> n_cities;
cin >> m_roads;

for (ulong i = 0; i ));
}

ulong v1, v2, cost;
ADJ_LIST_NODE node;
for (ulong i = 0; i > v1;
cin >> v2;
cin >> cost;

if (v1 >= n_cities or v2 >= n_cities) {
cout > src;
cin >> dest;
if (src >= n_cities or dest >= n_cities) {
cout > q_broken_roads;
if (q_broken_roads > m_roads) {
cout > r.v

Lets start with the explicit questions:


i am looking for advice on the following


will this read better if it is object oriented?

Most definitely. I have implemented this before; probably using less than a quarter of the lines of code shown here.


I guess that is a resounding yes.

Yes.


what kind of classes make sense? (one for adjacency list, one for list of closed roads and so on?)

Personally I think that's the wrong way to go. Just mark closed roads as having infinite cost.


is this design effort worth the time on coding competitions?

Depends on the goals of the competition. But I find that if you have a clear set of interacting classes then the it reduces the overall code size. This in turn will reduce the time it takes to write the code.


what are other glaring design errors in my code?

I will cover that below.


i know global vars are one.

Yes


sometimes i need multiple return values - do i make a struct for each of such type of return values?

No. There are a couple of utility classes that will help.


is there a less tedious design?

Yes. std::pair<> and std::tupple<> (boost::tupple<>) spring to mind.

Obvious hangovers from C

Stop using macros where they are not needed (and there are very few places they are needed). Macros should be used to do conditional compilation based on some factor not known at development time (OS/Compiler etc).

#define ulong unsigned long
#define INFINITY (ulong)-1

// Better to write as:
typedef unsigned long  ulong;
static ulong const INFINITY = static_cast(-1);

struct's no longer need a typedef in C++

typedef struct {
  ulong nbr;
  ulong cost;
} ADJ_LIST_NODE;

// Much more readable as:

// Remember all caps identifiers are traditionally reserved for macros.
// Best not to use them just in-case there is a clash.
struct AdjListNode  
{
  ulong nbr;
  ulong cost;
};

Comments about class names.

You class names are really horrible. It is really hard to understand what they are going to be used for: ADJ_LIST_NODE, SP_FOUND_NODE, SP_ESTIMATE_NODE, ROAD. About the only one I can guess at is ROAD. I assume the v1, v2 are the city IDs.

Also you in your code and comments you switch between two different naming schemes. You can refer to the data as a graph sometimes (vertices) and sometimes geographically (city/roads). If you stick to one metaphor while coding it makes it easy to visualize what you are trying to achieve.

C++ things you should stop doing

Stop doing using namespace std; its a bad habbit. It's not as if typing std:: infront of everything is going to cost you a lot of time.

Stop using C-Casts (ulong)-1. C-casts are hard to see (by reading)/ find(with the editor) and basically you are telling the compiler to shut up and accept your word that you are correct (thus you can easily miss mistakes). The C++ casts are a little more explicit in what they do and thus will catch many mistakes. Also they are easy to see and simple to search for using the editor.

C++ things I would change

class SPEstimateNodeCompare {
public:
  bool operator()(const SP_ESTIMATE_NODE& a, const SP_ESTIMATE_NODE& b) {
    return a.dist > b.dist;
  }
};

Here I would change the opeator() to be const

bool operator()(SP_ESTIMATE_NODE const& a, SP_ESTIMATE_NODE const& b) const {
                                                                //     ^^^^^^^

The other thing I would change is to put it into the SP_ESTIMATE_NODE class. The only time you use this is for sorting in a priority queue. So it is easier to define the priority queue if the class already intrinsicly knows how to sort itself.

struct SP_ESTIMATE_NODE
{
  ulong vertex;
  ulong dist;
  ulong predecessor;
  bool operator rhs.dist;}
};

Now your priority queue declaration becomes:

priority_queue   sp_estimate_q;

Also I would add constructors to your classes so that you can jsut create the elements in one go:

So if we add the constructor here:

struct SP_ESTIMATE_NODE
{
  SP_ESTIMATE_NODE(ulong v, ulong d, ulong p) : vertex(v), dist(d), predecessor(p) {}
  ulong vertex;
  ulong dist;
  ulong predecessor;
};

Then the following code:

est_node.vertex = next_road->first;
est_node.dist = next_road->second;
est_node.predecessor = src;
sp_estimate_q.push(est_node);

// can be simplifies to:

sp_estimate_q.push(SP_ESTIMATE_NODE(next_road->first, next_road->second, src));

Global variables

vector > city_adj_list;
ulong n_cities, m_roads;
ulong src, dest;
ulong q_broken_roads;
vector broken_road_list;

map sp_found;
priority_queue, SPEstimateNodeCompare > sp_estimate_q;
map estimate_distances;

Get rid of them. The side affects make it harder to remember things when modifying the code and also probably prevent the compiler optimizing the code as much as it could if you passed around things by parameter.

Spurious code:

In void read_input()

```
node.nbr = v2; // This and the next line seem like a complet wa

StackExchange Code Review Q#11101, answer score: 4