Dijkstra shortest path implementation for adjacency list represented graph

Question

Please review the implementation of Dijkstra algorithms. Points on which I have doubt:

1. My Graph doesn't have any ID for nodes. Nodes are accessed based on their data. Is there any general approach in that? Should nodes be referenced by an ID as that will also make these algo somewhat easier to implement by using id as index into arrays.

2. With current graph representation, are there any issue in the algo implementation?

3. Are there any issues in method of accessing vertex and edges shared_ptr? Should weak_ptr be used at some places? Any shared_ptr validity issue?

Anything that you can suggest to improve will be helpful.

Vertex:

class Vertex {
public:
    Vertex() {
        bVisited = false;
    }
    int data = 0;
    EdgeList edgeList;
    bool bVisited = false; 
};

Edge:

struct Edge {
    int cost;
    boost::weak_ptr<Vertex> srcVertex;
    boost::weak_ptr<Vertex> dstVertex;
};

Graph:

typedef std::list<boost::shared_ptr<Vertex>> VerticesList;
typedef std::map<int, VerticesList::const_iterator> DataVertexMap;
class Graph {

    VerticesList _verticesList;
    DataVertexMap _dataVertexMap;

    //TODO: Need some design to have this function internal only and not exposed to client
    boost::shared_ptr<Vertex> addAndGetVertex(int data);
public:
    Graph();
    ~Graph();

    bool isEmpty() const;
    //We don't check for duplicate vertex
    void addVertex(int data);
    void addEdge(int srcData, int dstData, int cost);
    int getCostForEdge(int srcData, int dstData);
    void displayGraph();
    void dfsTraversal();
    void bfsTraversal();

    void findShortestPath(int srcData, int dstData);
    void kruskalMST();
    void primMST();
};

Dijkstra's shortest path implementation:

void Graph::findShortestPath(int srcData, int dstData) {
    DataVertexMap::const_iterator srcIter = _dataVertexMap.find(srcData);
    DataVertexMap::const_iterator dstIter = _dataVertexMap.find(dstData);
    if(srcIter == _dataVertexMap.end() || dstIter == _dataVertexMap.end())
        assert(false);

    boost::shared_ptr<Vertex> srcVertex(*(srcIter->second));
    boost::shared_ptr<Vertex> dstVertex(*(dstIter->second));

    struct VertexInfo {
        bool bGotMinDistance = false;
        boost::weak_ptr<Vertex> precedingVertex;
        int distanceFromSource = INFINITY;
    };

    boost::shared_ptr<Vertex> currentVertex = srcVertex;

    typedef std::map<boost::shared_ptr<Vertex>, VertexInfo> VertexInfoMap;
    VertexInfoMap vertexInfoMap;
    for(boost::shared_ptr<Vertex> vertex : _verticesList) {
        VertexInfo info;
        if(vertex.get() == srcVertex.get()) {
            info.bGotMinDistance = true;
            info.distanceFromSource = 0;
            info.precedingVertex = boost::weak_ptr<Vertex> ();
        }
        vertexInfoMap.insert(std::make_pair(vertex, info));
    }


    while(currentVertex.get() != dstVertex.get()) {
        VertexInfo& curVertexInfo = vertexInfoMap[currentVertex];
        curVertexInfo.bGotMinDistance = true;
        boost::shared_ptr<Vertex> minDistVertex = currentVertex;
        int curMinDist  = INFINITY;
        for(auto iter = vertexInfoMap.begin(); iter != vertexInfoMap.end(); ++iter) {
            boost::shared_ptr<Vertex> vertex = iter->first;
            VertexInfo& vertexInfo = iter->second;
            if(!vertexInfo.bGotMinDistance) {
                int distFromCurToVertex = getCostForEdge(currentVertex->data, vertex->data);
                if(vertexInfo.distanceFromSource > distFromCurToVertex + curVertexInfo.distanceFromSource) {
                    vertexInfo.distanceFromSource = distFromCurToVertex + curVertexInfo.distanceFromSource;
                    vertexInfo.precedingVertex = currentVertex;
                }

                if(vertexInfo.distanceFromSource < curMinDist) {
                    curMinDist = vertexInfo.distanceFromSource;
                    minDistVertex = vertex;
                }
            }
        }
        currentVertex = minDistVertex;
    }

Answer 1

A few observations:

• Your graph is not actually using an adjacency list. For that you need a list of edges for every vertex.
• The bVisited field is unused and shouldn't be part of Vertex anyway; it belongs to the algorithm not the graph.
• Your data member is essentially acting as an ID.
• You don't actually need to fill the std::map with empty values. If you use the [] subscript for access, empty values will be created as needed.
• Your shortest path method need to return something.
• Your algorithm doesn't look like Dijkstra's algorithm: there is no unvisited set or an efficient list of neighbors and you need to handle the case of no path existing between the source and destination.