c++ - Implementing the k-shortest paths problem

Question

I have implemented a directed weighted graph using map.

struct Edge
{
    int destination;
    int weight;
    Edge(int, int);
};

private:
    int number;
    std::map<std::string, int> vertices;
    std::map<int, std::string> reverseV;
    std::map<int, std::vector<Edge>> vEdges;
public:
public:
    Graph();
    Graph(std::string);
    void addVertex(std::string);
    void addEdge(std::string, std::string, int);
    void ShortestPaths(std::string, std::string);
};

I have to implement function, which solves the k-shortest path routing. Here is the algorithm: https://en.wikipedia.org/wiki/K_shortest_path_routing

And here is my function:

void Graph::ShortestPaths(std::string from, std::string to);
int numberOfwantedPaths = 3; 
    //int sumW = 0;
    std::vector<std::string> path; 
    std::pair<std::vector<std::string>, int> pathANDsumW; 
    std::set<std::pair<std::vector<std::string>, int> > Allpaths; 


    path.push_back(from);
    pathANDsumW = make_pair(path, 0);
    
    std::map<int, int> numberOfpaths; 

    for (auto& it : this->reverseV) 
    {
        numberOfpaths[it.first] = 0;
    }

    std::priority_queue<std::pair<std::vector<std::string>, int>, 
        std::vector<std::pair<std::vector<std::string>, int>>, 
        std::greater<std::pair<std::vector<std::string>, int> > > MinHeap;

    MinHeap.push(pathANDsumW);

    while (!MinHeap.empty() && numberOfpaths[this->vertices[to]] < numberOfwantedPaths)
    {
        std::vector<std::string> tempPath = MinHeap.top().first;
        int sumW = MinHeap.top().second;
        std::string currKey = tempPath[tempPath.size() - 1]; 
        int currKeyVal = this->vertices[currKey];
        numberOfpaths[currKeyVal]++;
        MinHeap.pop();

        if (currKey == to)
        {
            Allpaths.insert(make_pair(tempPath, sumW));
            break;
        }
        if (numberOfpaths[currKeyVal] <= numberOfwantedPaths)
        {
            for (auto& it : this->vEdges[currKeyVal])
            {
                std::vector<std::string> newPath = tempPath;
                newPath.push_back(this->reverseV[it.destination]);
                if (newPath[newPath.size()-1] == to)
                {
                    Allpaths.insert(make_pair(newPath, sumW));
                }
                MinHeap.push(make_pair(newPath, sumW + it.weight));

            }
        }
    }
//printing part
    for (auto& it : Allpaths)
    {
        for (int i = 0; i < it.first.size(); i++)
        {
            std::cout << it.first[i] << " ";
            if (i < it.first.size() - 1)
            {
                std::cout << " -> ";
            }
        }
        std::cout << std::endl;
    }

I can't find the error. What am I doing wrong? It prints only one path 3 times.

question from:https://stackoverflow.com/questions/65848417/implementing-the-k-shortest-paths-problem

Answer 1

Waitting for answers