Implementation of Dijkstra's shortest path algorithm

Question

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 <iostream>
#include <queue>
#include <list>
#include <map>

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< map< ulong, ulong> > city_adj_list;
ulong n_cities, m_roads;
ulong src, dest;
ulong q_broken_roads;
vector<ROAD> broken_road_list;

map< ulong, SP_FOUND_NODE > sp_found;
priority_queue< SP_ESTIMATE_NODE, vector<SP_ESTIMATE_NODE>, SPEstimateNodeCompare > sp_estimate_q;
map< ulong, ulong> estimate_distances;

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

  for (ulong i = 0; i < n_cities; i++) {
    city_adj_list.push_back(*(new map<ulong, ulong>));
  }

  ulong v1, v2, cost;
  ADJ_LIST_NODE node;
  for (ulong i = 0; i < m_roads; i++) {
    cin >> v1;
    cin >> v2;
    cin >> cost;

    if (v1 >= n_cities or v2 >= n_cities) {
      cout << "Invalid input!" << endl;
      exit(-1);
    }

    node.nbr = v2;
    node.cost = cost;
    city_adj_list[v1][v2] = cost;

    node.nbr = v1;
    node.cost = cost;
    city_adj_list[v2][v1] = cost;
  }

  cin >> src;
  cin >> dest;
  if (src >= n_cities or dest >= n_cities) {
    cout << "Invalid input - source/destination!" << endl;
    exit(-1);
  }  

  cin >> q_broken_roads;
  if (q_broken_roads > m_roads) {
    cout << "Invalid input - q value!" << endl;
    exit(-1);
  }  

  for (ulong i = 0; i < q_broken_roads; i++) {
    ROAD r; 
    cin >> r.v1;
    cin >> r.v2;
    if (r.v1 >= n_cities or r.v2 >= n_cities) {
      cout << "Invalid input! broken roads." << endl;
      exit(-1);
    }
    broken_road_list.push_back(r);
  }
}

void print_input(vector< map <ulong, ulong> >& adj_list) {
  map< ulong, ulong >::iterator next_road;
  for (ulong i = 0; i < n_cities; i++) {
    cout << "CITY " << i << endl;
    for (next_road = adj_list[i].begin(); 
         next_road != adj_list[i].end(); 
         next_road++) {
      cout << "Neighbour " << next_road->first << " Cost " << 
        next_road->second << endl;
    }    
  }
}


void relax_estimates(ulong vertex, ulong shortest_dist, vector< map <ulong, ulong> >& adj_list) {
  if (vertex >= n_cities) {
    cout << "Invalid relax vertex " << vertex << endl;
  }
  //  cout << "Relaxing w.r.t. " << vertex << endl;
  map < ulong, ulong>::iterator next_road;

  // For each neighbour of relax vertex, 
  for(next_road = adj_list[vertex].begin();
      next_road != adj_list[vertex].end();
      next_road++) {
    // next_road->nbr ==> first/key
    // next_road->cost ==> second/value
    if (sp_found.count(next_road->first) == 0 and 
        next_road->second + shortest_dist < estimate_distances[next_road->first]) {
          estimate_distances[next_road->first] = next_road->second + shortest_dist;
          //      cout << "Relaxed distance to " << next_road->first << " to " << estimate_distances[next_road->first] << endl;

          SP_ESTIMATE_NODE x;
          x.vertex = next_road->first;
          x.dist = estimate_distances[next_road->first];
          x.predecessor = vertex;
          sp_estimate_q.push(x);
        }
  }
}


ulong get_shortest_path (vector< map <ulong, ulong> >& adj_list) {
  SP_ESTIMATE_NODE est_node;
  SP_FOUND_NODE found_node;

  // Initialize data structures
  for (ulong v = 0; v < n_cities; v++) {
    estimate_distances[v] = INFINITY;
    sp_found.erase(v);
  }
  while (!sp_estimate_q.empty()) {
    sp_estimate_q.pop();
  }

  found_node.shortest_dist = 0;
  found_node.predecessor = -1;
  sp_found[src] = found_node;

  //  list<ADJ_LIST_NODE>::iterator next_road;
  map <ulong, ulong >::iterator next_road;
  for (next_road = adj_list[src].begin(); 
       next_road != adj_list[src].end(); 
       next_road++) {
    // next_road->nbr ==> first/key
    // next_road->cost ==> second/value
    //    cout << "Adding " << next_road->first << " with dist " 
    //   << next_road->second << " to priority q" << endl;
    est_node.vertex = next_road->first;
    est_node.dist = next_road->second;
    est_node.predecessor = src;
    sp_estimate_q.push(est_node);
    estimate_distances[est_node.vertex] = est_node.dist;
  }

  ulong relax_vertex = src;
  ulong relax_vertex_dist = 0;
  while (!sp_estimate_q.empty()) {
    // Get smallest dist entry from q
    est_node = sp_estimate_q.top();

    // Make sure est_node is not a duplicate entry in priority queue
    if (sp_found.count(est_node.vertex) > 0) {
      // Do nothing except delete it from map and queue.
      sp_estimate_q.pop();
      estimate_distances.erase(est_node.vertex);
      continue;
    }

    // cout << "Picked vertex " << est_node.vertex << " with dist " 
    //   << est_node.dist << " from priority q" << endl;

    // Add to list of shortest path found vertices.
    found_node.shortest_dist = est_node.dist;
    found_node.predecessor = est_node.predecessor;
    sp_found[est_node.vertex] = found_node;

    // Relax all its neighbours.
    relax_vertex = est_node.vertex;
    relax_vertex_dist = est_node.dist;
    relax_estimates(relax_vertex, relax_vertex_dist, adj_list);

    // Remove the resolved vertex.
    estimate_distances.erase(est_node.vertex);  
    sp_estimate_q.pop();
  }


  // Print.
  cout << sp_found[dest].shortest_dist << endl;

  //  cout << endl;
  // cout << "Shortest distance " << sp_found[dest].shortest_dist << endl;
  // cout << "Path (in reverse) " << dest;
  // ulong v = dest;
  // while (v != src) {
  //   v = sp_found[v].predecessor;
  //   cout << " - " << v;
  // }
  // cout << endl;

  return 0;  
}

int main() {

  read_input();

  //  cout << ">>>>> Before broken roads " << endl;
  //  get_shortest_path(city_adj_list);

  for (ulong i = 0; i < q_broken_roads; i++) {
    vector< map< ulong, ulong> > city_broken_adj_list = city_adj_list;
    // ROAD      broken_road_list[i];
    ulong v1 = broken_road_list[i].v1;
    ulong v2 = broken_road_list[i].v2;

    city_broken_adj_list[v1].erase(v2);
    city_broken_adj_list[v2].erase(v1);
    //    cout << ">>>>> Broken road " << v1 << "==" << v2 << endl;
    //    print_input(city_broken_adj_list);
    get_shortest_path(city_broken_adj_list);

  }
}

Answer 1

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<ulong>(-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<(SP_ESTIMATE_NODE const& rhs) const { return dist > rhs.dist;}
};

Now your priority queue declaration becomes:

priority_queue<SP_ESTIMATE_NODE>   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< map< ulong, ulong> > city_adj_list;
ulong n_cities, m_roads;
ulong src, dest;
ulong q_broken_roads;
vector<ROAD> broken_road_list;

map< ulong, SP_FOUND_NODE > sp_found;
priority_queue< SP_ESTIMATE_NODE, vector<SP_ESTIMATE_NODE>, SPEstimateNodeCompare > sp_estimate_q;
map< ulong, ulong> 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 waste.
node.cost = cost;  // Just remove them
city_adj_list[v1][v2] = cost;

node.nbr = v1;     // Same comment as above.
node.cost = cost;
city_adj_list[v2][v1] = cost;

Broken road list?

Why keep a separate list of broken roads. It would seem easier if you could just mark the roads themselves as broken.

I am not convinced that is dyxtra's algorithm

It should look like this:

 void find_shortest(int start, int end, std::vector<std::map<ulong,unlong>>& graph)
 {
     std::set<unlong>                              searchedList;
     std::priority_queue<std::pair<ulong, ulong>>  frontierList;

     // frontier list contains pairs of (cost, city)
     // std::pair is sorted by first then second so the frontierList
     // is automatically sorted by the cost of getting to a city.
     // Add the start city as the only city in the frontier list.
     frontierList.push(std::make_pair(0, start));

     while(!frontierList.empty())
     {
         std::pair<ulong, ulong> next = frontierList.top();
         frontierList.pop();

         if (next.second == end)
         {
             std::cout << "Min Cost: " << next.first << "\n";
             return;
         }
         if (searchedList.find(next.second) != searchedList.end())
         {
             continue; // We already found this node. move on.
             // Note: continue starts the next loop iteration.
         }
         // We have found the lowest cost to this city.
         // So mark that information by placing it in the searched list.
         searchedList.insert(next.second);

         // Add all city's that can be reached from here to the frontier list.
         for(std::map<ulong,unlong>::const_iterator loop = graph[next.second].begin(); loop != graph[next.second].end(); ++loop)
         {
             // Add item for each city (cost = cost to get here + cost of road)
             frontierList.push(std::make_pair(next.first + loop->second, loop->first));
         }
     }
 }

As you can see my implementation is a lot simpler than yours. I am not sure what you are trying to achieve with the relax method (it actually made my less relaxed trying to read it).