Dijkstra's algorithm using a specific structure

Question

I have implemented Dijkstra's algorithm using a slightly modified version of the structure and class posted here. Unfortunately, I have ruined the efficiency. I am intent on using this structure. I will NOT use BOOST. Any STL algorithms are acceptable.

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <list>
#include <set>
#include <algorithm>
struct vertex {
    typedef std::pair<double, vertex*> vert;                                      // weight, destination pair
    std::vector<vert> adj;                                                        // vector holding <weight of edge, destination vertex>
    std::string name;                                                             // to hold name/title of vertex
    vertex(std::string str) : name(str) {}                                        // struct constructor pass name to vertex.name
};

class graph {

    typedef std::map<std::string, vertex *> vertmap;                              // name, vertex pair
    vertmap port;                                                                 // map holding <name of vertex, pointer to vertex>
    std::vector<std::string> travel;                                              // vector holds BFS, DFS, or shortest distance
    typedef std::pair<std::string, bool> visited;                                 // visited name, bool pair
    void depthFirstUtil(const std::string&);                                      // helper for depth first search
    vertex* addvertex(const std::string&);                                        // add a vertex to the graph
public:
    graph() { }
    graph(std::vector<vertex*> edges);
    void addedge(const std::string&, const std::string&, const double);           // add a weighted edge to the graph
    std::vector<std::string> getDepthFirst(const std::string&);
    std::vector<std::string> getBredthFirst(const std::string&);
    typedef std::pair<double, std::string> dPair;
    std::vector<dPair> getShortestDistance(const std::string&);
};

int main() {
    graph mygraph;
    std::string myverts[6] = { "v0", "v1", "v2", "v3", "v4", "v5" };
    mygraph.addedge(myverts[0], myverts[1], 2);
    mygraph.addedge(myverts[0], myverts[5], 9);
    mygraph.addedge(myverts[1], myverts[2], 8);
    mygraph.addedge(myverts[1], myverts[3], 15);
    mygraph.addedge(myverts[1], myverts[5], 6);
    mygraph.addedge(myverts[2], myverts[3], 1);
    mygraph.addedge(myverts[4], myverts[2], 7);
    mygraph.addedge(myverts[4], myverts[3], 3);
    mygraph.addedge(myverts[5], myverts[4], 3);

    std::cout << "Depth first: ";
    for (auto ver : mygraph.getDepthFirst(myverts[0])) std::cout << ver << " ";
    std::cout << std::endl << std::endl << "Bredth first: ";
    for (auto ver : mygraph.getBredthFirst(myverts[0])) std::cout << ver << " ";
    std::cout << std::endl << std::endl << "Shortest distance: " << std::endl;
    for (auto ver : mygraph.getShortestDistance(myverts[0])) std::cout << ver.second << " " << ver.first << std::endl;
    system("pause");
    return 0;
}

graph::graph(std::vector<vertex*> edges) {
    for (auto edge : edges) for (auto dest : edge->adj) addedge(edge->name, dest.second->name, dest.first);
}

void graph::depthFirstUtil(const std::string& inName) {
    travel.push_back(inName);                                                                   // mark inName as visited
    std::vector<vertex::vert> avec = port.at(inName)->adj;                                      // Recur for all the vertices adjacent to this vertex
    for (auto i : avec) 
        if (std::find(travel.begin(), travel.end(), i.second->name) == travel.end()) 
            depthFirstUtil(i.second->name);
}

std::vector<std::string> graph::getDepthFirst(const std::string& begin) {   
    travel.clear();                                                                             // Mark all the vertices as not visited
    depthFirstUtil(begin);                                                                      // Call the recursive helper function to print DFS traversal
    return travel;
}

std::vector<std::string> graph::getBredthFirst(const std::string& name) {
    travel.clear();
    std::list<std::string> queue;                                                               // Create a queue for BFS
    queue.push_back(name);
    while (!queue.empty()) {
        travel.push_back(queue.front());                                                        // Dequeue a vertex from queue and store it
        queue.pop_front();
        for (auto i : port.at(travel.back())->adj)                                              // Get all adjacent vertices of the dequeued vertex 
            if((std::find(travel.begin(), travel.end(), i.second->name) == travel.end())        // If an adjacent vertex has not been visited, then enqueue it
                && (std::find(queue.begin(), queue.end(), i.second->name) == queue.end()))      // IF NOT IN TRAVEL AND NOT IN QUEUE!
                queue.push_back(i.second->name);
    }
    return travel;
}

vertex* graph::addvertex(const std::string &name) {
    vertmap::iterator itr = port.find(name);
    if (itr == port.end()) {
        vertex *v = new vertex(name);
        port[name] = v;
        return v;
    }
    else return itr->second;
}

void graph::addedge(const std::string& from, const std::string& to, const double weight) {
    vertex *f = (addvertex(from));
    vertex *t = (addvertex(to));
    std::pair<double, vertex *> edge = std::make_pair(weight, t);
    f->adj.push_back(edge);
}


typedef std::pair<double, std::string> dPair;
std::vector<dPair> graph::getShortestDistance(const std::string& start) {
    travel.clear();
    std::vector<dPair> nameDist;
    std::vector<dPair> nameDistCopy;
    std::string vertName;
    std::set<vertex*> queue;
    double totDist;
    for (auto i : port) {
        dPair portPair = std::make_pair(INFINITY, i.first);
        nameDist.push_back(portPair);
        nameDistCopy.push_back(portPair);
        queue.insert(i.second);
    }
    auto srcItr = std::find_if(nameDist.begin(), nameDist.end(), [=](const dPair vName) {
        return vName.second == start;
    });
    double minDist = (*srcItr).first = 0;
    while (!queue.empty()) {
        auto vNameItr = std::min_element(nameDistCopy.begin(), nameDistCopy.end());
        vertName = (*vNameItr).second;
        minDist = (*std::find_if(nameDist.begin(), nameDist.end(), [=](const dPair element) {
            return element.second == vertName;
        })).first;
        auto qVertItr = std::find_if(queue.begin(), queue.end(), [=](const vertex* element) {
            return element->name == vertName;
        });
        vertex *minVert;
        minVert = *qVertItr;
        queue.erase(minVert);
        for (auto neighbor : minVert->adj) {
            totDist = minDist + neighbor.first;
            auto distItr = std::find_if(nameDist.begin(), nameDist.end(), [=](const dPair vName) {
                return vName.second == neighbor.second->name;
            });
            if (totDist < (*distItr).first) {
                (*distItr).first = totDist;
            }
        }
        auto erItr = std::find_if(nameDistCopy.begin(), nameDistCopy.end(), [=](const dPair vName) {
            return vName.second == minVert->name;
        });
        nameDistCopy.erase(erItr);
    }
    return nameDist;
}

I would very much appreciate any/all optimization of the getShortestDistance function. I am fine with the implementation of the other functions.

Answer 1

Yes, your implementation of Dijkstra's shortest path algorithm is far from efficient. Here is a pseudo code for a better one:

DijkstraSearch(graph g, int source, int target):
    OPEN = std::priority_queue<int>
    CLOSED = std::unordered_set<int>
    parent_map = std::unordered_map<int, int>
    distance_map = std::unordered_map<int, double>

    OPEN.push(source)
    parent_map[source] = source
    distance_map[source] = 0.0

    while (OPEN not empty):
        current = OPEN.extractMinimum()
        if current is target:
             return traceback_path(source, target, parent_map)
        if CLOSED contains current:
             continue
        CLOSED.add(current)

        for neighbor in graph.neighbors_of(current):
            if CLOSED contains neighbor:
                continue
            double tentative_distance = distance_map[current] + graph.weight(current, neighbor)
            if neighbor not in parent_map.keys() or tentative_distance < distance_map[neighbor]:
                distance_map[neighbor] = tentative_score
                parent_map[neighbor] = current
                OPEN.insert(neighbor, tentative_distanse) # insert(node, priority)
    error "No path"

traceback_path(source, target, parent_map):
    path = []
    current = target
    while (true):
         path.append(current)
         current = parent_map[current]
         if current == source:
              break
    path.reverse()
    return path

If implemented correctly, the above will run in \$\mathcal{O}((m + n) \log n)\$. If you, however, use a Fibonacci heap, the running time will improve to \$\mathcal{O}(m + n \log n)\$.

Answer 2

Actually, the algorithm posted by op (me) fails to function properly. If you were to input "v5" as the starting point, the only results would be the distances from "v5" to "v5" == 0, and "v5" to "v4" == 3. The intent of the algorithm (in this case) is to return the shortest distance from some arbitrary starting vertex to each vertex in the graph. To remedy this only (does NOT improve efficiency), the starting vertex should be set to 0 in both the nameDist pair and the nameDistCopy pair. Further, when the total distance is less than the currently stored nameDist pair it should be updated in both nameDist and nameDistCopy.