Implementation of Dijkstra's algorithm to find the shortest path in graph

Question

This is my implementation of Dijkstra's algorithm in C++.

Please clarify

1. Whether the class design is proper or if it needs to be improved.
2. I am just hard coding the vertex based on the priority of the vertex. Is there is any other way to implement it?
3. Please provide some suggestions to optimize the code.

class Vertex
{
public:
    int m_id;
    unsigned int m_cost;
    bool m_isVisited;

    std::map<int,unsigned int> m_edgeList; // map to store neighbour nodes and cost to reach them

    void findMinDistance(std::vector<Vertex>&);

    Vertex(int p_id)
    {
        m_id= p_id;
        if(p_id == 0)
        {
            m_cost=0;
        }
        else
        {
            m_cost=UINT_MAX; // Assigning Infinite cost
        }
        m_isVisited=false;
    }

    Vertex()
    {           
    }
};

void Vertex::findMinDistance(std::vector<Vertex> &p_vertex)
{

    m_isVisited= true;
    // Looping throgh the neighbour list and update cost 
    for(std::map<int,unsigned int>::iterator iter = m_edgeList.begin();
        iter!=m_edgeList.end(); iter++)
    {
        //If cost of picked neighbour is greater than current_vertex+new cost then replace cost
        if ( p_vertex.at(iter->first).m_isVisited == false && p_vertex.at(iter->first).m_cost > m_cost+(iter->second))
        {
            p_vertex.at(iter->first).m_cost=m_cost+iter->second;

            std::cout<<"\nVertex Id : "<<p_vertex.at(iter->first).m_id;
            std::cout<<"\nExisting Cost  : "<<p_vertex.at(iter->first).m_cost;          
            std::cout<<"\nNew Cost : "<<p_vertex.at(iter->first).m_cost;
        }
    }
}

int main()
{
    std::vector<Vertex> l_vertex;

    for(int i=0; i<7;i++)
    l_vertex.push_back(Vertex(i)); // Push Vertex to vector container

    // updating the edges and cost to respective node
    // The below model is similar to priority queue.

    l_vertex.at(0).m_edgeList.insert(std::make_pair((l_vertex.at(5).m_id),14));
    l_vertex.at(0).m_edgeList.insert(std::make_pair((l_vertex.at(2).m_id),9));
    l_vertex.at(0).m_edgeList.insert(std::make_pair((l_vertex.at(1).m_id),7));


    l_vertex.at(1).m_edgeList.insert(std::make_pair((l_vertex.at(0).m_id),7));
    l_vertex.at(1).m_edgeList.insert(std::make_pair((l_vertex.at(2).m_id),10));
    l_vertex.at(1).m_edgeList.insert(std::make_pair((l_vertex.at(3).m_id),15));

    l_vertex.at(2).m_edgeList.insert(std::make_pair((l_vertex.at(0).m_id),9));
    l_vertex.at(2).m_edgeList.insert(std::make_pair((l_vertex.at(5).m_id),2));
    l_vertex.at(2).m_edgeList.insert(std::make_pair((l_vertex.at(3).m_id),11));
    l_vertex.at(2).m_edgeList.insert(std::make_pair((l_vertex.at(1).m_id),10));

l_vertex.at(5).m_edgeList.insert(std::make_pair((l_vertex.at(0).m_id),14));
l_vertex.at(5).m_edgeList.insert(std::make_pair((l_vertex.at(2).m_id),2));
l_vertex.at(5).m_edgeList.insert(std::make_pair((l_vertex.at(4).m_id),9));

l_vertex.at(4).m_edgeList.insert(std::make_pair((l_vertex.at(5).m_id),9));
l_vertex.at(4).m_edgeList.insert(std::make_pair((l_vertex.at(3).m_id),6));

l_vertex.at(3).m_edgeList.insert(std::make_pair((l_vertex.at(4).m_id),6));
l_vertex.at(3).m_edgeList.insert(std::make_pair((l_vertex.at(2).m_id),11));
l_vertex.at(3).m_edgeList.insert(std::make_pair((l_vertex.at(1).m_id),15));



// updating cost of each vertex by calling findMinDistance

for(std::vector<Vertex>::iterator iter = l_vertex.begin(); iter != l_vertex.end(); iter++)
{
    (*iter).findMinDistance(l_vertex);
}

for(int i=0;i<6;i++)
std::cout<<"\n\nshortest "<<i<<" "<<l_vertex.at(i).m_cost;

return 0;
}

Answer 1

This is a bad idea:

class Vertex
{
public:
    int m_id;
    >>> unsigned int m_cost;
    >>> bool m_isVisited;

You are conflating two things into a single class. The concept of a vertex and the concept of performing Dijkstra's algorithm on the node. You should separate the two issues into their own classes.

The main problem with this technique is that you need to reset the graph before use. ie. you can not run your algorithm twice in a row. You must reset the state of the whole graph before it can be re-used. Look up the visitor pattern.

You really want a constructor that does no initialization?

Vertex()
{           
}

The POD members will be left in an undefined state.

Your have void findMinDistance(std::vector<Vertex>&); in the vertex? Find min distance to where?

Use the new C++ range based for:

for(std::map<int,unsigned int>::iterator iter = m_edgeList.begin();
    iter!=m_edgeList.end(); iter++)

// can be rewritten as:
for(auto& edge: m_edgeList)

Overall I don't think you are actually implement Dijkstra's algorithm.

Dijkstra algorithm

The algorithm should look like this (this is pseudo code).
The classic part is the frontier list (I called it boundryList) and the set of vertex we have found the shortest route to.

 RouteCostObject findRout(Graph& g, Vertex& start, Vectex& end)
 {
      OrderedListByDistance    boundryList;
      SetOfVertex              foundVertixes;

      boundryList.push_back([start, 0, []]);

      while(!boundryList.empty())
      {
          // Remove the top items from the list.
          (vertex, cost, route) = boundryList.top();       // Note: boundryList is sorted
          boundryList.pop();

          // If we have reached the end.
          // This is the shortest route.
          if (vertex == end)
          {    return [cost, route];
          }


          // Check if we have already found the shortest distance
          // to this vertex.
          if (foundVertixes.find(vertex) != vertex.end())
          {
              continue;
          }
          foundVertixes.insert(vertex);

          // Add all edges to the boundary list.
          for(auto& edge: vertex.edges)
          {
              boundryList.push_back([edge.dst, cost + edge.cost, route + edge]);
          }
      }
      // No route from start to end
      return [infinity, []];
 }

Answer 2

• The four variables in Vertex should be private. This should always be done with a class' data members to prevent them from exposing the implementation details.

• The conditional in Vertex's constructor:

  if(p_id == 0)
  {
      m_cost=0;
  }
  else
  {
      m_cost=UINT_MAX; // Assigning Infinite cost
  }
  

  can be shortened to a single-line ternary statement:

  m_cost = (p_id == 0) ? 0 : UINT_MAX;
  

• findMinDistance() probably should need to display anything. Something like that should either be handled directly in main() or be put into either a display function or operator<<. This will allow more flexible displaying while keeping the I/O separate.

• The indentation in main() is quite inconsistent. The lines towards the end should be aligned with the earlier code, which is already indented properly.

  This is also messy:

  for(int i=0; i<7;i++)
  l_vertex.push_back(Vertex(i));
  

  This should use more whitespace, indentation, and curly braces:

  for (int i = 0; i < 7; i++)
  {
      l_vertex.push_back(Vertex(i));
  }
  

  The same applies to this:

  for(int i=0;i<6;i++)
  std::cout<<"\n\nshortest "<<i<<" "<<l_vertex.at(i).m_cost;
  

  It should look similar to the first example:

  for (int i = 0; i < 6; i++)
  {
      std::cout << "\n\nshortest " << i << " " << l_vertex.at(i).m_cost;
  }